Otdfbt

I am watching this professor's video on Binary Search but when he reached here, I am a bit lost. How come he came up the time coomplexity is log in just by breaking off binary tree and knowing height is log n
https://youtu.be/C2apEw9pgtw?t=969 . and then the time complexity become log 16/2 = 4... how that is $log n$ time complexity?

Here's an answer to the question

How come the time complexity of Binary Search is $log n$?

that describes informally what's going on in the binary tree in the question and in the video (which I have not watched).

You want to know how long binary search will take on input of size $n$, as a function of $n$.

At each stage of the search (pass through the body of the while loop) you split the input in half, so you successively reduce the size of the problem (h-l) this way:
$$
n, n/2, n/4, n/8 ldots .
$$
(Strictly speaking, you round those to integers.)

Clearly you will be done when the input is $1$, for there's just one place. That index is the answer.

So you want the number of steps $k$ such that $n/2^k le 1$. That's the smallest $k$ for which $2^k ge n$. The definition of the logarithm says that $k$ is about $log_2(n)$, so binary search has that complexity.

How come he came up the time coomplexity is log in just by breaking off binary tree and knowing height is log n

I'm guessing this is a key part of the question: you're wondering not just "why is the complexity log(n)?", but "why does knowing that the height of the tree is log2(n) equate to the complexity being O(log(n))?"

The answer is that steps down the tree are the unit "operations" you're trying to count. That is, as you walk down the tree, what you're doing at each step is: "[check whether the value at your current position is equal to, greater than, or less than the value you're searching for; and accordingly, return, go left, or go right]". That whole chunk of logic is a constant-time-bounded amount of processing, and the question you're trying to answer is, "How many times (at most) am I going to have to do [that]?"

For every possible search, you'll be starting at the root and walking down the tree, all the way (at most) to a leaf on the bottom level. So, the height of the tree is equal to the maximum number of steps you'll need to take.

One other possible source of confusion is that seeing him draw the whole tree might give the impression that the search process would involve explicitly constructing the entire Binary Search Tree data structure (which would itself be a O(n) task). But no -- the idea here is that the tree exists abstractly and implicitly, as a graph of the relationships among the elements in the array; and drawing it and tracing paths down it is just a way of visualizing what you're doing as you jump around the array.

First, it is important to note that the running time of an algorithm is usually represented as function of the input size. Then, we 'measure' the complexity by fitting this function into a class of functions. For instance, if $T(n)$ is the function describing your algorithm's running time and $gcolonmathbbNtomathbbR$ is another function then
$$Tin O(g) iff text there exist c,n_0inmathbbR_++ text such that T(n)leq c g(n) text for each ngeq n_0. $$

Similarly, we say that

$$Tin Omega(g) iff text there exist c,n_0inmathbbR_++ text such that T(n)geq c g(n) text for each ngeq n_0. $$

If $T$ belongs to both $O(g)$ and $Omega(g)$ then we say that $TinTheta(g)$. Let's conclude that for the binary search algorithm we have a running time of $Theta(log(n))$. Note that we always solve a subproblem in constant time and then we are given a subproblem of size $fracn2$. Thus, the running time of binary search is described by the recursive function $$T(n)=TBig(fracn2Big)+alpha.$$
Solving the equation above gives us that $T(n)=alphalog_2(n)$. Choosing constants $c=alpha$ and $n_0=1$, you can easily conclude that the running time of binary search is $Theta(log(n))$.