2
$\begingroup$

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?

enter image description here

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So basically, in this case log2(𝑛) is simplified as log n in the lecture. correct? $\endgroup$ – Ezeewei May 13 at 14:27
  • 7
    $\begingroup$ @Ezeewei Correct. In computer science just plain $\log$ usually means $\log_2$. In mathematics it usually means $\ln = \log_e$. It hardly ever means $\log_{10}$ these days. All those logs are proportional, so for big-O time complexity arguments they are the same. $\endgroup$ – Ethan Bolker May 13 at 14:29
  • 2
    $\begingroup$ Yes. In time complexity we don't care about multiplicative factors. $\log n = \log 2 \log_2 n$. In fact most logs in complexity work are taken to base $2$ $\endgroup$ – Ross Millikan May 13 at 14:30
  • 2
    $\begingroup$ @Chris All logs are the same for the complexity analysis. Base $2$ is what comes up naturally for this algorithm, and for most estimates in theoretical computer science. If you happen to be working with a divide-and-conquer algorithm that trisects its input you would work in base $3$. $\endgroup$ – Ethan Bolker May 13 at 16:32
  • 1
    $\begingroup$ @Chris We're not always doing big-O analysis. Sometimes you actually want a more precise calculation. Also, even with big-O, something like $O(2^{\log n})$ would be sensitive to the base of the logarithm. $\endgroup$ – Derek Elkins May 13 at 20:19
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 $g\colon\mathbb{N}\to\mathbb{R}$ is another function then $$T\in O(g) \iff \text { there exist } c,n_0\in\mathbb{R}_{++} \text{ such that } T(n)\leq c g(n) \text{ for each } n\geq n_0. $$

Similarly, we say that

$$T\in \Omega(g) \iff \text { there exist } c,n_0\in\mathbb{R}_{++} \text{ such that } T(n)\geq c g(n) \text{ for each } n\geq n_0. $$

If $T$ belongs to both $O(g)$ and $\Omega(g)$ then we say that $T\in\Theta(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 $\frac{n}{2}$. Thus, the running time of binary search is described by the recursive function $$T(n)=T\Big(\frac{n}{2}\Big)+\alpha.$$ Solving the equation above gives us that $T(n)=\alpha\log_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))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.