Question

topic is Algorithms, where you see O it means big O.please solve and explain

Is 2^(n+1) = O(2^(2n)) ? Is 2^(2n) = O(2^n)?

Answer 1

1)
2^(n+100) = O(2^n): Yes

Proof:
--------
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^1*2^n <= c(2^n)
Let's assume c = 2
=>  2*2^n <= c(2^n)
=>  2*2^n <= 2(2^n)
=>  2^n <= 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):  No

Proof:
--------
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)