1
$\begingroup$

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.

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

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) $.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please explain the solution using master theorem?. $\endgroup$ – Thinker May 21 '18 at 5:39
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 21 '18 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.