Question

Algorithm problem

4 [3.1-4] Is (2^(n+1))∈O(2^n)? Is (2^(2n))∈O(2^n)?

Answer 1

1)
2^(n+1) = O(2^n)
This is true.
let's prove it.

f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
2^(n+1) = O(2^n)
=>  2^(n+1) <= c(2^n)
=>  2*2^n <= c(2^n)
Let's assume c = 2
=>  2*2^n <= c(2^n)
=>  2*2^n <= 2(2^n)
=>  2*2^n <= 2*2^n
it's true for all n >= 1

so, 2^(n+1) = O(2^n) given c = 2 and n0 = 1

2)
2^2n = O(2^n)
This is not correct.
let's prove 2^(2n) is not O(2^n).

f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
assume 2^2n = O(2^n)
=>  2^2n <= c(2^n)
=>  2^n <= c
2^2n can be O(2^n) only if c >= 2^n

for f(n) = O(g(n)) then c must be a constant. here c >= 2^n which is not a constant
so, f(n) is not O(g(n))

hence 2^(2n) is not O(2^n)


Answer:
---------
Is (2^(n+1))∈O(2^n) Yes 
Is (2^(2n))∈O(2^n) No