How to derive the size of $k = \log n$ base from $\frac{1}{2^k} = O(\frac{1}{n})$?

"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?

• That doesn't really make sense because $\frac{1}{n} = O(1)$. Unless they mean $\Theta(\frac{1}{n})$ – ratchet freak Jun 26 '17 at 9:10
• 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. – 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)$$

• 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! – Joe Lilleberg Jun 26 '17 at 3:47