The algorithm A has a worstcase running time Tn 2n1 Is Tn

The algorithm A has a worst-case running time T(n) = 2^n_1 Is T(n) = O(n^3)?

Solution

Ans) No,T(n)!=O(n3) because O is an upper bound .To say that something has an upper bound of \"atleast\" x means its could be less than x.

Correct answer is T(n)=O(2^n) beacause 2^n+1=2*2^n=O(2^n)

Suppose 2^2n =O(2^n),then there exist a constant c such that for n beyond some n0,2^2n<=c2^n.Divide both side by 2^n,we get 2^n<c There is no value for c and n0 that can make this true,so the hypothesis is false 2^2n!=O(2^n).