3
$\begingroup$

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method:

$$T(n) = 4T(n/3) + n \log \log n$$

I want to try and use the master method to solve this, but somebody told me I can't, I'm not sure why. I couldn't really figure out how to use a recursion tree to solve this either (It seems to get pretty messy). Anyway, is master method a valid way to solve this problem? Thanks.

$\endgroup$
0
1
$\begingroup$

At least in some formulations of the Master Theorem (such as that found on Wikipedia), the relevant case for the recurrence $$ T(n) = a T(n/b) + f(n) $$ requires that $f(n)$ is $\Theta(n^c)$ for some $c<\log_b a$. And that condition is not exactly satisfied for $f(n)= n\log \log n$.

However, that difference doesn't really matter -- it's just a case of the theorem being formulated with stricter premises than necessary. In fact, if we consider the two recurrences $$ S(n) = 4(n/3) + n $$ $$ U(n) = 4(n/3) + n^{1+\varepsilon} $$ then the master theorem will apply to them and say that $S(n)$ and $U(n)$ are both $\Theta(n^{\log_3 4})$. Since we also eventually have $S(n) < T(n) < U(n)$, this bound is good for $T$ too.

So the theorem could just as well have required only that $f(n)=O(n^c)$ for some $c<\log_b a$ instead of $\Theta(n^c)$ -- and thus corrected it does indeed apply to your recurrence.

$\endgroup$
0
$\begingroup$

As it is, you can't use Master Theorem for this recurrence: the term $f(n) = n\log\log n$ is not in any of the three forms required by the three cases of the theorem. A trick that might work is finding a substitution that transforms the recurrence in one of these forms.

$\endgroup$
4
  • $\begingroup$ Okay so maybe a sub like m = logn? $\endgroup$ – Mathew Feb 3 '14 at 4:22
  • 1
    $\begingroup$ On the other hand, the $T$ is clearly eventually between the result of the recurrence if we replace $n\log \log n$ with either $n$ or $n^{1+\varepsilon}$. And the theorem in those two cases give the same bound for $T$, which is therefore also a tight bound of the original recurrence. It's just a matter of the formulation of the master theorem (at least in the shape Wikipedia gives it) being sloppy and not exposing the full power of it. $\endgroup$ – hmakholm left over Monica Feb 3 '14 at 4:24
  • $\begingroup$ @HenningMakholm Uh, right! Thank you for making me think about this issue in its formulation. $\endgroup$ – Jacopo Notarstefano Feb 3 '14 at 4:30
  • $\begingroup$ But when I do a substitution like m = lgn I end up having to express n like 2^m which is not allowed in master theorem. $\endgroup$ – Mathew Feb 3 '14 at 5:40
0
$\begingroup$

Let me point out that as others have observed we can spot the complexity right away without making much of an effort. It is clear that the contribution of the recursive term outgrows that of the work term. It is possible however to find an exact solution to a related recurrence that has the same complexity.

Suppose we have the following recurrence for $T(n)$ where $T(0)=0$, $T(1)=c_1$ and $T(2)=c_2$ and for $n\ge 3,$ $$T(n) = 4 T(\lfloor n/3 \rfloor) + n \lfloor\log \lfloor \log_3 n \rfloor\rfloor.$$ Furthermore suppose that the representation of $n$ in base three is given by $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k.$$ Then it is not difficult to see that $T(n)$ for $n\ge 3$ has the exact closed form $$T(n) = [d_{\lfloor \log_3 n \rfloor}=1] c_1 4^{\lfloor \log_3 n \rfloor} + [d_{\lfloor \log_3 n \rfloor}=2] c_2 4^{\lfloor \log_3 n \rfloor} \\+ \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} \lfloor \log (\lfloor \log_3 n \rfloor - j) \rfloor 4^j \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j}.$$ Now to get bounds on this we need an upper and a lower bound on the sum term. For an upper bound consider a string of two-digits, which gives $$\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} \lfloor \log (\lfloor \log_3 n \rfloor - j) \rfloor 4^j \times 2 \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} 3^{k-j} \\ = \sum_{j=0}^{\lfloor \log_3 n \rfloor-1} \lfloor \log (\lfloor \log_3 n \rfloor - j) \rfloor 4^j \times (3^{\lfloor \log_3 n \rfloor+1-j}-1) \\ = \sum_{j=1}^{\lfloor \log_3 n \rfloor} \lfloor \log j \rfloor 4^{\lfloor \log_3 n \rfloor-j} \times (3^{j+1}-1) = 4^{\lfloor \log_3 n \rfloor} \sum_{j=1}^{\lfloor \log_3 n \rfloor} \lfloor \log j \rfloor 4^{-j} \times (3^{j+1}-1).$$ The sum term converges to a number, which is about $$6.271543822.$$ For a lower bound consider a one digit followed by a string of zeros, which gives $$\sum_{j=0}^{\lfloor \log_3 n \rfloor-1} \lfloor \log (\lfloor \log_3 n \rfloor - j) \rfloor 4^j \times 3^{\lfloor \log_3 n \rfloor -j} \\ = \sum_{j=1}^{\lfloor \log_3 n \rfloor} \lfloor \log j \rfloor 4^{\lfloor \log_3 n \rfloor-j} \times 3^j = 4^{\lfloor \log_3 n \rfloor} \sum_{j=1}^{\lfloor \log_3 n \rfloor} \lfloor \log j \rfloor (3/4)^j.$$ The sum term again converges to a number, which in this case is $$2.097465834.$$

We are done with our investigation because both the upper and the lower bound term have been shown to consist entirely of contributions that are asymptotic to $4^{\lfloor \log_3 n \rfloor}$ (this includes the two terms in the leading digit Iverson bracket). Hence our final complexity is $$ \Theta\left(4^{\lfloor \log_3 n \rfloor}\right) = \Theta\left(4^{\log_3 n} \right) = \Theta\left(3^{\log_3 4 \times \log_3 n}\right) = \Theta\left(n^{\log_3 4}\right)$$ as predicted by inspection.

This MSE link features another Master Theorem computation that uses the same technique.

$\endgroup$

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.