Since $2^n = O(2^{n-1})$, does the transitivity of $O$ imply $2^n=O(1)$?

174 Views Asked by At

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions.

Now, use limit to find $O(f(n))$: $\lim_{n\to\infty} \dfrac{2^{n+1}}{2^n}=2$. This is not equal to infinity, so the limit exists, hence $2^{n+1}$ belongs to $O(2^n)$.

Now, according to transitivity property: $$2^n=O(2^{n-1}), \;2^{n-1}=O(2^{n-2}),\;\ldots ,\;2^i=O(2^{i-1})$$ so using transitivity property we can write $2^{n+1}=O(2^{i-1})$. We can go on extending this so that finally $2^{n+1}= O(2^k)$, where $k$ is constant. So we can write $2^{n+1}=O(1)$. Do you agree with what has been proved? If not, where is the fallacy?

1

There are 1 best solutions below

0
On BEST ANSWER

No, this is not true.

For a fixed $n$ you have $2^n \le \alpha_n$ for some $\alpha_n \gt 0$. This is generally obvious, since $2^n$ is some number, but your "proof by induction" basically proves the same. Note that $\alpha_n$ is depending on $n$.

But: $2^n = \mathcal{O}(1)$ would imply that $2^n \le \alpha$ for all $n$ and just one $\alpha$. That‘s not possible of course.

Or in other words: It is true that $2^n = \mathcal{O}(2^{n-k})$ for any fixed $k$, but $k$ may not depend on $n$.