1
$\begingroup$

$$T(1) = 2$$ $$T(n) = T(\frac{n}{3}) + 6^n \text{ For n > 1}$$

I tried using the substitution method to find it's closed form but I even from there, I could not figure out how to find its bound. My working:

$k = 1$ $$T(n) = T(\frac{n}{3}) + 6^n $$ $k = 2$ $$T(n) = T(\frac{n}{9}) + (6^{\frac{n}{3}})+(6^n) $$ $k = 3$ $$T(n) = T(\frac{n}{27})+ (6^{\frac{n}{9}}) + (6^{\frac{n}{3}})+(6^n) $$ $k = 4$ $$T(n) = T(\frac{n}{81}) + (6^{\frac{n}{27}}) + (6^{\frac{n}{9}}) + (6^{\frac{n}{3}})+(6^n) $$

From the pattern, I can guess that it has the following recurrence

$$T(n) = T(\frac{n}{3^k}) + (k)(6^n) $$

Solving for $k$ we have

$1 = \frac{n}{3^k}$

$3^k = n$

$\log{_3}{n} = k$

Substituting all the k we have

$T(n) = 2 + 6^n\log{_3}{n}$

I'm stuck over here. Can master theorem apply for this case? Is there an upperbound for $k^n$ ?

$\endgroup$
1
  • 1
    $\begingroup$ You messed up substitution on step $k=2$. It should yield $T(n)=\sum_{i=0}^{\log_3 n}6^{n/3^i}$ instead. The terms drop off so fast in value that I see no reasonable way to sum them compactly. Basically we have $T(n)\sim 6^n$ - only the first term matters. $\endgroup$
    – A.S.
    Commented Nov 17, 2015 at 3:35

1 Answer 1

0
$\begingroup$

Hint:

$$6^n > n^{\log_3 2}$$

Can you take another look at the Master theorem cases ?

$\endgroup$
3
  • $\begingroup$ Apologies, can you give me more hints? Looking at the master theorem, I will need to find an upper bound for $6^n$. I realized that the upper bound would be an exponential upper bound. I don't see how the master theorem works in this case $\endgroup$
    – TheValars
    Commented Nov 16, 2015 at 19:11
  • 1
    $\begingroup$ Case $3$, where $f(n) \in \Omega(n^{\log_b a+ \epsilon}) $, with $\epsilon > 0$. In our case $f(n) = 6^n, b = 3, a= 1$ and I took the liberty of setting $\epsilon = 1$. $\endgroup$
    – Victor
    Commented Nov 16, 2015 at 19:13
  • $\begingroup$ Actually, I don't think that passes the regularity condition. $\endgroup$
    – TheValars
    Commented Nov 17, 2015 at 1:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .