algoritham

Question

T(n) = T(n/2)+2^{​​​​​n} find the complexity? 

A) O(n log n)

B)O(n²)

C)O(2ⁿ)

D) O(n)

Comments

@anup here, we are reducing the problem by half in each step and we are doing some work of $O(2^n)$. So, it's sufficient enough here to say that (C) is answer.

---

Thank you..

---

@mcjoshi, I got the logic. Is it possible to solve this recurrence relation by substitution?

---

Is it possible by master's theorem 3rd case?

---

Yes, it is possible to do it using substitution and for master's theorem see example-3 here

Answer 1

by applying master theorem 

if n^logb(a) is >f(n) then tc=o(n^logb(a))

else n^logb(a)==f(n) then tc=o(n^logb(a)logn)

else o(f(n))

coming to given problem

n^log2(1)<2^n

then TC=O(2^n)