1
$\begingroup$

n < $2^n$ whenever n is a positive integer. Show that this inequality implies that n is $O(2^n)$ and use this inequality to show that log n is O(n). There is a book solution but I am having a hard time understanding in laymans terms.

Solution: Using the inequality $n < 2^n$, we quickly can conclude that n is $O(2^n)$ by taking k = C = 1 as witnesses. Note that because the logarithm function is increasing, taking logarithms (base 2) of both sides of this inequality shows that $logn < n$. It follows that log n is O(n). (Again we take C = k = 1 as witnesses.) If we have logarithms to a base b, where b is different from 2, we still have $\log_b n$ is O(n) because

$\log_b n = \frac{\log n}{ log b} < \frac{n}{ log b}$

whenever n is a positive integer. We take C = 1/ log b and k = 1 as witnesses.

So, how do we conclude n is $O(2^n)$? Using log rules but how do we know its increasing? This is where I start to get lost and it makes it hard to piece together the rest of the solution. Please help.

$\endgroup$
3
  • $\begingroup$ So, you want to know why $n$ is $O(2^n)$? You've answered this in your own question: $n < 2^n$ for all $n \ge 1$. Do you want to prove this inequality? Or do you not understand how this inequality implies $n$ is $O(2^n)$? $\endgroup$ Oct 2, 2018 at 4:14
  • $\begingroup$ @Theo Bendit its hard for me to understand why $n$ is $O(2^n)$. Why is it not O(n)? and then, assuming the base is changed to b which is any number not 2, why did the function divide $log_b$? $\endgroup$
    – JScribe
    Oct 2, 2018 at 4:23
  • $\begingroup$ @Theo Bendit My understanding so far: $n < 2^n$ whenever n is a positive integer implies that at some point, k, $2^n$ function will grow faster than function n. n> 1 C and k are positive constants and therefore the function is continuously increasing. Log rules may apply. So, $n < 2^n = log_2(n) < log_2(2^n) = log_2(n) < n$ $\endgroup$
    – JScribe
    Oct 2, 2018 at 4:24

1 Answer 1

0
$\begingroup$

Recall the definition of $f(n) \in O(g(n))$: there exists some $k$ and $C > 0$ such that

$$n \ge k \implies |f(n)| \le C|g(n)|.$$

We have $n < 2^n$, as in the question, for $n \ge 1$. Therefore, taking $k = 1$ and $C = 1$, we have $$n \ge 1 \implies |n| = n \le 2^n = |2^n|$$ so $n \in O(2^n)$.

But, you're also right that $n \in O(n)$ too. These are not mutually exclusive. We have $$n \ge 1 \implies |n| \le |n|,$$ which shows $n \in O(n)$. In fact, if $f(n) \in O(g(n))$ and $g(n) \in O(h(n))$, then it's a good exercise to show that $f(n) \in O(h(n))$.

You said, in the comments, that your understanding of $n < 2^n$ implies that at some point $k$, $2^n$ will grow faster than $n$. It's not entirely clear what you mean here, but I wouldn't sweat it too much. The point is, $2^n$ starts bigger than $n$, and stays that way forever afterwards, fulfilling the requirement for $n \in O(2^n)$.


Now, consider the case where $b \neq 2$. This is one situation where I think the book needs a little bit more detail. In particular, I think we should also assume $b > 1$. The case for $0 \le b \le 1$ should be handled separately (and the $b < 0$ case handled separately again). I will assume $b > 1$.

Since $\log_2 n < n$ for all $n \ge 1$, we can use the change of base formula. Recall that $$\log_b n = \frac{\log_2 n}{\log_2 b}.$$ (If you don't accept this formula, try looking it up online.) But, since $b > 1$, it follows that $\frac1{\log_2 b} > 0$, so $$\log_2 n < n \implies \log_b n = \frac{\log_2 n}{\log_2 b} < \frac{1}{\log_2 b} n.$$ This proves that $\log_b n \in O(n)$, using $C = \frac{1}{\log_2 b}$.

$\endgroup$
1
  • $\begingroup$ Wow thank you for the extensive answer! I was definitely sweating small details but I see now how they are all conversion-able just considering a different C and conditions and using log rules. We just learned change of base so I should have thought about that. Thank you for your time and knowledge. $\endgroup$
    – JScribe
    Oct 2, 2018 at 5:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .