Time Complexity Problem

129 Views Asked by At

The asymptotic notation $O$ satisfies the transitive property, i.e. if $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$.

Now, $2^{n+1}$ = $O(2^n)$. Extending this further, we can write $2^n = O(2^{n-1})$, . . . , $2^i = O(2^{i−1})$.

Using the transitive 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 a constant. So, we can write $2^{n+1} = O(1)$.

Question: Do you agree to what has been proved? If not, where is the fallacy?

1

There are 1 best solutions below

0
On

The fallacy is that $O$ notation only applies to functions, not numbers. So it is true that, writing $f_i$ for the function $f_i:n\mapsto 2^{n-i}$, we have $f_i=O(f_{i+1})$ for every $i$. But there is no $i$ for which $f_i$ is constant.

What does follow from this argument is that the function $g:x\mapsto 2^n$ is $O(1)$ (as $x\to\infty$) for every $n$. But as a function of $n$, $2^n$ is not $O(1)$.