0
$\begingroup$

I know that:

If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that

$f(n) <= M*g(n), \forall n > n_0$

The other, plain English way of defining it is,

If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would grow as fast as $g(n)$.

I got confused when comparing $2^n$ with $2^{2n}$. Here , $f(n) = 2^n$ and $g(n) = 2^{2n}$. Clearly , $f(n)$ is smaller than $g(n)$ by a factor of $2^n$. So there will be constants $A$ and $x_0$ such that the first definition above is met.

However, for large $n$ , $2^{2n}$ would grow much faster than $2^n$, leaving $2^n$ far behind. That is $2^{2n}$ won't be an asymptotic/tight bound for $2^n$ .

So, is $2^n = O(2^{2n})$ or not? (or did I just create a confusing situation out of nothing)

$\endgroup$
4
$\begingroup$

The more strong estimate is correct:

$2^n = o(2^{2n})$

Just look at definition of the little-o. For any constant $c \gt 0$ you need to find a constant $n_0$, such that for all $n \ge n_0$ you get $2^n \le c \cdot 2^{2n}$. Apparently, the following inequality will give you this $n_0$:

$n_0 \ge ln(1 / c)$

$\endgroup$
  • $\begingroup$ Thanks. Little-O is apt for comparing $2^n$ with $2^{2n}$ $\endgroup$ – sanjeev mk Feb 16 '14 at 5:44
3
$\begingroup$

Remember that $O$ is an upper bound.

$2^n = O(2^{2n})$, but $4^n = 2^{2n} \ne O(2^n)$. I.e., $2^{2n}$ is not within a constant factor of $2^n$.

$\endgroup$
3
$\begingroup$

The statement:

If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would grow as fast as $g(n)$.

is incorrect, and that's probably where your confusion is. Taking from Raphael's answer in How does one know which notation of time complexity analysis to use? :

$f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$...

Note "at most as fast," not "as fast." If you want "as fast," you're probably looking for $\Theta$; taking from Raphael's answer again:

$f \in \Theta(g)$ means that $f$ grows about as fast as $g$...

but as you've already probably guessed, $2^n \notin \Theta(2^{2n})$. For $2^n \in \Theta(2^{2n})$ to be true, $2^{2n}$ would itself have to be $\cal{O}$$(2^n)$, which I think you can see is clearly not the case.

$\endgroup$
  • $\begingroup$ Thanks Dennis. From Raphael's answer and especially about $<$ being stricter than $<=$ , it is clear that $2^n = o(2^{2n})$ , because $2^n$ for all positive constants $c$ will be strictly smaller than $c *\space 2^{2n}$ $\endgroup$ – sanjeev mk Feb 16 '14 at 5:46

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.