I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree of the subroutines and see how each level k behaves, right?

Now suppose your divide-and-conquer algorithm can be described as the following:

$T(n) = T(\frac{n}{2}) + 1.5^n$

My guess is that this is $\theta(1.5^n)$ simply because it would seem this term dominates, but I have little logical backing for my guess. How would you find the big theta to this task?

My attempt to find the answer was to draw out the first few levels of the tree, finding:

Level 1: $T(n) = 1.5^n$

Level 2: $T(n) = 1.5^{\frac{n}{2}}$

Level 3: $T(n) = 1.5^{\frac{n}{4}}$

So it seems for level k (starting at 1), the task comes out to be $1.5^{\frac{n}{2^{k-1}}}$

So as the amount of levels increase, it seems the time to perform the task is decreasing by a factor of 2?

Any help is welcome! Hints are preferred, but if you wish to provide the full answer that is fine too.

  • $\begingroup$ You can upper bound the sum by the sum of geometric progression, and the lower bound is trivial. $\endgroup$ – diplodoc Sep 10 '19 at 16:44
  • $\begingroup$ $a=1, r=1.5, n=n$. $\endgroup$ – diplodoc Sep 10 '19 at 16:56
  • $\begingroup$ because the sum is bounded by $\sum_{i=0}^nr^i = \frac{r^{n+1}-1}{r-1}$ $\endgroup$ – diplodoc Sep 10 '19 at 17:06
  • $\begingroup$ Yes, your guess is correct $\endgroup$ – diplodoc Sep 10 '19 at 17:10

Your Answer

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