I ran a program to find the difference between n + 1 and 2**ceil(log2(n+1)),where n is a power of 2 . It keeps increasing exponentially
So from the definition of Big - O, there is no constant c' such that -
2^(2^ceil(log2(n))) <= c' * 2^n
Therefore
(2^(2^ceil(log2(n)))) != O( 2^n )
Would the above statement be correct ? If yes, then how can I prove it ?
We need to show that, for every constant c, there exists n such that 2^(2^ceil(log2(n))) > c * 2^n. Let's consider only n = 2^k + 1 for some integer k > 1; this is our right, since we are not trying to prove the statement for all n. The desired inequality becomes
2^(2^ceil(log2(2^k + 1))) >? c * 2^(2^k + 1).
We simplify the left hand side.
ceil(log2(2^k + 1)) = k + 1
2^(2^ceil(log2(2^k + 1))) = 2^(2^(k + 1)).
The desired inequality is
2^(2^(k + 1)) >? c * 2^(2^k + 1).
This inequality is equivalent to
2^(2^(k + 1) - 2^k - 1) = 2^(2^k - 1) >? c.
2^k - 1 >? log2(c)
2^k >? log2(c) + 1
k >? log2(log2(c) + 1).
The choice of k (and thus n) is now obvious; work backward through the inequality to show the desired inequality, so the function is not O(2^n).