Answer and explain (no explanation - no credit): i. Is 2^(n+64) = O(2^n)? Why? ii. Is 2^3n = O(2^2n)? Why?

i. No, 2^(n+64) is not O(2^n). The reason is that 2^(n+64) = 2^n * 2^64. The factor of 2^64 means that the function 2^(n+64) grows exponentially faster than 2^n. In Big O notation, we say that a function f(n) is O(g(n)) if there are positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n > n0. In this case, there is no constant c that would make the inequality 0 ≤ 2^(n+64) ≤ c2^n true for all n > n0.

ii. Yes, 2^3n is O(2^2n). The reason is that 2^3n = (2^2n) * (2^n). Even though 2^3n grows faster than 2^2n, it is still bounded above by a constant multiple of 2^2n for sufficiently large n. In Big O notation, we say that a function f(n) is O(g(n)) if there are positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n > n0. In this case, we can choose c = 2^n and n0 = 1 to make the inequality 0 ≤ 2^3n ≤ c2^2n true for all n > n0.