"We need $k$ to be large enough so that $(\frac{1}{2})^k = O(\frac{1}{n})$, and to do this we can choose $k = \log_2 n$. Thus, when $k = \log_2 n$, the size of the active region has been reduced to a constant, at which point the recursion bottoms out and we can search the remainder of the array directly in constant time."

Im not certain on how they determine that $k$ needs to be $\log_2 n$ from $(\frac{1}{2})^k = O(\frac{1}{n})$. Can someone please clarify the logic for this please?

  • $\begingroup$ That doesn't really make sense because $\frac{1}{n} = O(1)$. Unless they mean $\Theta(\frac{1}{n})$ $\endgroup$ – ratchet freak Jun 26 '17 at 9:10
  • $\begingroup$ I mean $\frac{1}{n} = O(1)$ would only be true if n were integers, but if it's in the domain of real numbers then it doesn't hold. In my statement, they were trying to find k to match the runtime of the algorithm which in my case was the binary search algorithm. $\endgroup$ – Joe Lilleberg Jun 26 '17 at 19:40

Think about it if we remove the fraction. We need a $k$ large enough so that $2^k = O(n)$. We could do this simply by solving for $k$ in the expression $2^k = n$. Which is simply $k = \log_2 n$. This is because $2^{\log_2 n} = n$.

Now apply the same logic to your expression, with $k = \log_2 n$ we see that: $$\frac{1}{2^{\log_2 n}} = \frac{1}{n} = O\left(\frac{1}{n}\right)$$

| cite | improve this answer | |
  • $\begingroup$ Ah, I was trying to apply the log is a completely different way and it became a mess. I can't believe I overlooked this... thank you very much! $\endgroup$ – Joe Lilleberg Jun 26 '17 at 3:47

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.