# Can Master Theorem be applied on any of these?

1) $T(n) = 6T(n/2) + 2^{3 \log(n)}$
2) $T(n) = 8T(n/2) + \frac{n^3}{(\log(n))^4}$
3) $T(n) = 9T(n/3) + n(\log(n))^3$

Can the complexity for these be calculated with the Master Theorem? I am not sure how to decide upon which case they fit in.

• Note that $2^{3\log(n)}=n^3$, I assumed by $\log$ you mean $\log_2$ Commented Dec 6, 2013 at 20:01

For problem three, lets solve the recurrence $$T(n) = 9 T(\lfloor n/3\rfloor) + n \times (1+\lfloor\log_3 n\rfloor)^3$$ where we set $T(0)=0.$

Let the base three representation of $n$ be $$n = \sum_{k=0}^{\lfloor\log_3 n\rfloor} d_k 3^k.$$

Then we get the exact formula $$T(n) = \sum_{j=0}^{\lfloor\log_3 n\rfloor} 9^j \times (1+\lfloor\log_3 n\rfloor- j)^3 \times \sum_{k=j}^{\lfloor\log_3 n\rfloor} d_k 3^{k-j} \\ = \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times (1+\lfloor\log_3 n\rfloor - j)^3 \times \sum_{k=j}^{\lfloor\log_3 n\rfloor} d_k 3^k .$$

Now for an upper bound consider a string of two digits, which gives $$T(n)\le \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times (1+\lfloor\log_3 n\rfloor - j)^3 \times 2 \times \sum_{k=j}^{\lfloor\log_3 n\rfloor} 3^k \\ = \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times (1+\lfloor\log_3 n\rfloor - j)^3 \left(3^{\lfloor\log_3 n\rfloor + 1}-3^j\right) \\ = \sum_{j=1}^{\lfloor\log_3 n\rfloor+1} 3^{\lfloor\log_3 n\rfloor+1-j} \times j^3 \times \left(3^{\lfloor\log_3 n\rfloor + 1}-3^{\lfloor\log_3 n\rfloor + 1- j}\right) \\ = 3^{2(\lfloor\log_3 n\rfloor + 1)} \sum_{j=1}^{\lfloor\log_3 n\rfloor+1} 3^{-j} j^3 (1- 3^{-j}).$$ Now the sum term converges to a constant and we get the upper bound $$\frac{7917}{2048} \times 3^{2(\lfloor\log_3 n\rfloor + 1)}.$$ For the lower bound take a one followed by a string of zeros, which gives $$T(n)\ge \sum_{j=0}^{\lfloor\log_3 n\rfloor} 3^j \times (1+\lfloor\log_3 n\rfloor - j)^3 \times 3^{\lfloor\log_3 n\rfloor} \\ = 3^{\lfloor\log_3 n\rfloor} \sum_{j=1}^{\lfloor\log_3 n\rfloor+1} 3^{\lfloor\log_3 n\rfloor +1 -j} \times j^3 = 3^{2\lfloor\log_3 n\rfloor + 1} \sum_{j=1}^{\lfloor\log_3 n\rfloor+1} j^3 3^{-j}.$$ The sum term again converges to a constant and we get for the lower bound asymptotics the formula $$\frac{33}{8} 3^{2\lfloor\log_3 n\rfloor + 1} .$$ Note that for the upper bound we have $\lfloor\log_3 n\rfloor+1\to\log_3 n,$ so that it is in fact $$\frac{7917}{2048} n^2 \approx 3.86572265625\times n^2$$ but for the lower bound $\lfloor\log_3 n\rfloor = \log_3 n$, so that it is $$\frac{33}{8} \times 3 \times n^2 = \frac{99}{8} n^2 \approx 12.375 \times n^2.$$

Joining the two bounds we may conclude that $$T(n)\in \Theta\left(3^{2\lfloor\log_3 n\rfloor}\right) = \Theta(n^2).$$

A similar computation which is a bit simpler can be used to analyse the cost of Strassen matrix multiplication.

You may be interested to know that there are exact solutions to your three problems. We will do problem one and provide references for the other two.

Suppose we have $T(0)$ and for $n\ge 1$ we have the recurrence $$T(n) = 6 T(\lfloor n/2 \rfloor) + 2^{3\lfloor \log_2 n \rfloor}.$$ We can unroll this recurrence to obtain the exact result that $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 6^j \times 2^{3(\lfloor \log_2 n \rfloor - j)}.$$ This simplifies to $$T(n) = 2^{3\lfloor \log_2 n \rfloor} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\frac{6}{8}\right)^j = 2^{3\lfloor \log_2 n \rfloor} \frac{1-(3/4)^{\lfloor \log_2 n \rfloor +1}}{1-3/4} \\ =4 \times 2^{3\lfloor \log_2 n \rfloor} \left(1-(3/4)^{\lfloor \log_2 n \rfloor +1}\right).$$ The conclusion is that $$T(n) \in \Theta\left(2^{3\lfloor \log_2 n \rfloor}\right) = \Theta(n^3).$$

This MSE link points to a series of similar calculations.

For your second problem, lets solve the recurrence $$T(n) = 8 T(\lfloor n/2 \rfloor) + \frac{n^3}{(1+\lfloor\log_2 n\rfloor)^4}$$ where $T(0) = 0.$

Let $$n = \sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k$$ be the binary representation of $n.$ Unrolling the recursion we find the exact formula $$T(n) = \sum_{j=0}^{\lfloor\log_2 n\rfloor} \frac{8^j}{(1+\lfloor\log_2 n\rfloor - j)^4} \left(\sum_{k=j}^{\lfloor\log_2 n\rfloor} d_k 2^{k-j}\right)^3.$$

Now to get an upper bound on this consider the case of $n$ being a string of one digits, which gives $$T(n)\le \sum_{j=0}^{\lfloor\log_2 n\rfloor} \frac{8^j}{(1+\lfloor\log_2 n\rfloor - j)^4} \left(\sum_{k=j}^{\lfloor\log_2 n\rfloor} 2^{k-j}\right)^3 \\ = \sum_{j=0}^{\lfloor\log_2 n\rfloor} \frac{1}{(1+\lfloor\log_2 n\rfloor - j)^4} \left(\sum_{k=j}^{\lfloor\log_2 n\rfloor} 2^k\right)^3 = \sum_{j=0}^{\lfloor\log_2 n\rfloor} \frac{1}{(1+\lfloor\log_2 n\rfloor - j)^4} (2^{\lfloor\log_2 n\rfloor+1} - 2^j)^3 \\ = \sum_{j=1}^{\lfloor\log_2 n\rfloor+1} \frac{1}{j^4} (2^{\lfloor\log_2 n\rfloor+1} - 2^{\lfloor\log_2 n\rfloor+1-j})^3 = 2^{3(\lfloor\log_2 n\rfloor+1)} \sum_{j=1}^{\lfloor\log_2 n\rfloor+1} \frac{1}{j^4} (1 - 2^{-j})^3.$$ The sum term converges rapidly to a constant and hence the asymptotics of the upper bound are $$\frac{1}{90} \left(\pi^4 -270 \mathrm{Li}_4(1/2) + 270 \mathrm{Li}_4(1/4) - 90 \mathrm{Li}_4(1/8)\right) \times 2^{3(\lfloor\log_2 n\rfloor+1)}.$$

For the a lower bound consider the case of a one digit followed by zeros, which gives $$T(n)\ge \sum_{j=0}^{\lfloor\log_2 n\rfloor} \frac{8^j}{(1+\lfloor\log_2 n\rfloor - j)^4} \left(2^{\lfloor\log_2 n\rfloor-j}\right)^3 = 2^{3\lfloor\log_2 n\rfloor}\sum_{j=0}^{\lfloor\log_2 n\rfloor} \frac{1}{(1+\lfloor\log_2 n\rfloor - j)^4} \\ = 2^{3\lfloor\log_2 n\rfloor}\sum_{j=1}^{\lfloor\log_2 n\rfloor+1} \frac{1}{j^4} .$$ The sum term once again converges to a constant and the asymptotics of the lower bound are $$\frac{\pi^4}{90} 2^{3\lfloor\log_2 n\rfloor}.$$

Joining the two bounds we see that $$T(n) \in \Theta\left(2^{3\lfloor\log_2 n\rfloor}\right) = \Theta(n^3).$$

• Yes, thank you that is very helpful indeed . But i was also wondering if we could obtain the same result with the Master Theorem? I am trying to understand how to solve such recurrences easier with it.
– Alex
Commented Dec 7, 2013 at 19:50
• Just compute $\log_b a$ as described in the Wikipedia entry. For the first question you get a value less than three and $2^{3\lfloor\log_2 n\rfloor}$ is $\Theta(n^3)$, so $n^3$ dominates. For the second problem, we get $\log_b a = 3$ so the recursive term dominates, again giving $n^3$. For the third case, you get $\log_b a = 2$, so the recursive term dominates. I will check problem three using my method. Commented Dec 7, 2013 at 21:35