Complexity

Question

Answer 1

in c option 
it says f(n)<=2ⁿ⁺¹⁰ 
        here f(n)=2^n-4
means 
2^n-4 <=2ⁿ⁺¹⁰
2ⁿ * 2^-4 <=2ⁿ  * 2¹⁰

2^-4 <=C * 2¹⁰

where c is constant for c>0
there fore c option is true..
 

 similarly for (a) option there exist a positive constant for which this function  is theta of n hence true 
also we can both are asymptotically equal so (a) option is true.

(b) option  

f(n)>=n¹⁰⁰⁰
2^n-4 >=n¹⁰⁰⁰
asymptotically  we can say :2ⁿ >=n¹⁰⁰⁰ 

apply log both side 
n * log 2 >=C * (10000log n)
clearly LHS is bigger so this option also true 
so (d) answer..

correct me  if any mistake thanks...
 

Answer 2

Ans : (b)

For very large value of n , n-10 ≈ n-4 ≈  n+3 ≈  n

Hence f(n)  = O(2^n-10) ≈  O(2ⁿ) and Also  f(n)  = 2ⁿ⁺³  ≈  2ⁿ => f(n)  = Ω(2ⁿ)  => f(n)  = Θ(2ⁿ)

Now since f(n) > n¹⁰⁰⁰ but f(n) ≥ 2ⁿ  Hence 2ⁿ  asymptotically tight lower bound. Hence f(n)  = Ω(2ⁿ)

Hence f(n)  = Ω(n¹⁰⁰⁰) is false.

Hence option (b) is answer.