# What would be the time complexity for following recurrence?

T (n) = T (n/2) + 2^n

I am solving this using master theorem and I calculated it to be big theta(log2 n) (log n to the base 2). But answer state it to be 2^n.

Any help would be appreciated.

• The recurrence has no time complexity, just like it has no color and no mother tongue. – Yuval Filmus May 20 '18 at 20:45

You asked for a solution with the Master Theorem, so let's have a look;

Define your Function as $T(n) = a \cdot{} T \left( \frac{n}{b} \right) + f(n)$. Here you have $a = 1$, $b = 2$ and $f(n) = 2^n$.

Master Theorem has 3 main cases (e.g. shown here):

Case 1 - $f(n) \in \mathcal{O} \left( n^{\log_b(a)-\epsilon{}} \right)$ with $\epsilon > 0$

Case 2 - $f(n) \in \Theta \left( n^{\log_b(a)} \log^k n \right)$ with $k \geq 0$

Case 3 - $f(n) \in \Omega \left( n^{\log_b(a) + \epsilon} \right)$ and $a \cdot f \left( \frac{a}{b} \right) \leq c \cdot f(n)$ for large $n$ and some constant $c < 1$

Let's check, which one applies: Inserting $a$ and $b$ into $\log_b(a)$ gives $\log_2(1) = 0$ we get $n^{\log_b(a)} = n^0 = 1$ resulting into $f(n) \in \Omega \left( n^{\log_b(a) + \epsilon} \right)$.

The other precondition also holds obviously (just put in the numbers for $a$ and $b$ and find a $c$ for yourself).

This results in the 3rd case of the Master Theorem, giving $T(n) \in \Theta (f(n)) = \Theta (2^n)$.

You mention applying the master theorem and obtaining the solution $T(n) = \Theta(\log_2 n)$. However, assuming that $T(1) \geq 0$, it is clearly the case that $T(n) \geq 2^n$. So you must have applied the master theorem in the wrong way.

In your particular case, you can also just expand the recurrence. Assuming that $n$ is a power of 2 and a base case $T(1) = C \geq 0$, we get $$T(n) = 2^n + 2^{n/2} + 2^{n/4} + \cdots + 2^2 + C.$$ This is clearly at least $2^n$. If $m \geq 2$ then $m/2 \leq m-1$. Applying this inductively, we see that \begin{align*} T(n) &\leq 2^n + 2^{n-1} + 2^{n-2} + \cdots + 2^{n-\log_2 n + 1} + C \\ &\leq 2^n + 2^{n-1} + \cdots + 2^0 + C \\ &= 2^{n+1} - 1 + C \\ &= O(2^n). \end{align*} Therefore $T(n) = \Theta(2^n)$. With only a little more effort, we can get \begin{align*} T(n) &\leq 2^n + 2^{n/2} + 2^{n/2-1} + \cdots + 2^{n/2 - \log_2 n + 2} + C \\ &\leq 2^n + 2^{n/2} + 2^{n/2-1} + \cdots + 2^0 + C \\ &= 2^n + 2^{n/2+1} - 1 + C = 2^n + O(2^{n/2}), \end{align*} implying the stronger estimate $T(n) \sim 2^n$.

• Can you please explain the solution using master theorem?. – Thinker May 21 '18 at 5:39
• You choose the correct line in the table, and you get the correct result. I'm not sure what exactly went wrong in your attempt, since you haven't explained your reasoning. – Yuval Filmus May 21 '18 at 5:41