1
$\begingroup$

My question is that can we say that runtime of the binary search is $\Omega(\log n)$?

I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst case. And for this reason the time complexity of binary search is $\Theta(\log n)$.

However, I still cannot interpret if it is also $\Omega(\log n)$ even if I think (and know that) it is. So, I just need some scientific explanation.

$\endgroup$
1
$\begingroup$

To prove the lowerbound of $\Omega(\mathrm{log}n)$, it is best to use an adversary argument.

For each $n$, you can fix some pattern of access when running binary search, i.e. a sequence of $Left-Half$, $Right-Half$ of length $log(n)/2$, then put the searched value at the index when you go according to that sequence.

For the remaining of the array, just put in arbitrary value such that they are all less than the searched value at the lesser index and larger than the searched value at higher index.

$\endgroup$
2
$\begingroup$

First, you can analyze the time complexity of binary search in whatever case you wish, say "best case" and "worst case". In the best case, you use $f(n)$ time, while in the worst case you use $g(n)$ time. These are two functions of $n$, describing two different scenarios you have defined. Now, you can make statements such as $f(n) = O(1)$ or $g(n) = \Theta(\log n)$. However, the Big Oh of a function has nothing to do with time complexity, it is merely something applied to a function that could just as well be representing the number of apples you get for $n$ euros.

In particular, thinking along the lines of "$O$ is always for best case, $\Omega$ is for the worst case" (or whatever), is wrong and dangerous.

To you specific question: if a function $g(n) = \Omega(\log n)$ and $g(n) = O(\log n)$, then $g(n) = \Theta(\log n)$. The function $g(n)$ might be representing the time complexity of binary search or the number of apples, it doesn't matter. And as always, look at the definitions and you can stop guessing.

$\endgroup$
  • $\begingroup$ thanks for answering. From your answer I think we can also say runtime of sorted-BS is also O(N)? can we say that too? $\endgroup$ – WhoCares Oct 24 '18 at 9:25
  • $\begingroup$ @WhoCares I can definitely help you answer this. At least in principle, how could we determine whether it is $O(n)$? $\endgroup$ – Juho Oct 24 '18 at 9:48
  • $\begingroup$ I don't know. you tell me. I am soo confused anymore :/ $\endgroup$ – WhoCares Oct 24 '18 at 10:48
  • $\begingroup$ @WhoCares The answer is in the last sentence of my answer: look at the definition. So what do you need to do to determine if $f(n) = O(n)$? $\endgroup$ – Juho Oct 24 '18 at 11:24
  • $\begingroup$ We can't get any faster than O(log n), but we may get any slower than O(log n) like O(n) ? Is that the thing you want me to understand? $\endgroup$ – WhoCares Oct 24 '18 at 11:26

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.