2
$\begingroup$

This is a homework question about using Master's theorem, and I can't seem to wrap my head around this question:

$$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$

I've tried to apply the Master's theorem to this question like any other Master's theorem questions: $$a=2,b=3\, \text{ and }\, f(n)=(\lg(n))^2.$$

Now, I need to figure out which case this condition falls into.
$$n^{\lg_b(a)}=n^{\lg_3(2)}=n^{0.631}$$

But the problem is that I cannot express f(n) as a polynomial for comparison as shown below:
$$n^{\lg_b(a)+\epsilon}$$

How would I figure out which case of Master's theorem this lie on?

Would taking logarithms of both sides for comparison make sense since logarithm is a monotonic function?
$$2\cdot \lg(\lg(n)) \quad\text{and} \quad (0.631+\epsilon)\cdot \lg(n)$$

Then figure out what epsilon is ...

Thank you in advance,
kpark

$\endgroup$
  • $\begingroup$ I edit (add $\LaTeX$) your question. If I changed anything wrong please let me know. $\endgroup$ – Cortizol Sep 13 '13 at 20:17
  • $\begingroup$ @Cortizol thank you cuz I have no idea how to use latex. I should really learn.. $\endgroup$ – kpark Sep 14 '13 at 16:39
1
$\begingroup$

A log-power $(\log n)^k$ is $O(n^c)$ for any $c > 0$. In other words, a power of $\log n$ grows more slowly than any positive power of $n$. (You can show this by evaluating $\lim_{n \to \infty} (\log n)^k / n^c$ using L'Hopital's rule repeatedly.) So you can assume that your additive function $f(n) = (\log n)^2$ satisfies $f(n) = O(n^c)$ for whatever low enough positive $c$ you need to satisfy the conditions of the Master theorem to show that the running time is the smallest possible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow thank you, I had no idea that (log n)^k = O(n^c) for any c > 0. Just one more additional question to verify: Does this mean (log n)^100 = O(n)? $\endgroup$ – kpark Sep 14 '13 at 16:45
  • $\begingroup$ Yes. =) Any power of $\log n$ will be $O(n)$, or even $O(n^{0.01})$ or $O(n^c)$ for any $c > 0$. $\endgroup$ – user2566092 Sep 30 '13 at 17:04
1
$\begingroup$

There is a closely related recurrence that has the same complexity and can be solved exactly. This is the recurrence that has $T(0) = 0$ and $T(1) = 1$ and $$T(n) = 2 T(\lfloor n/3\rfloor) + (1+\lfloor\log_3 n\rfloor)^2.$$ To verify that the complexity is the same note that $1+\lfloor\log_3 n\rfloor -\log_3 n \le 1$ and that $\log_3 n \in\theta(\log n).$

Now this recurrence is not difficult to solve exactly, we have that $$T(n) = \sum_{k=0}^{\lfloor\log_3 n\rfloor} 2^k (\lfloor\log_3 n\rfloor + 1 - k)^2.$$ This solution is particularly simple as it does not depend on the actual values of the digits in base three of $n$ but only on their number (if the added term were $n(\lfloor\log_3 n\rfloor + 1)$, for example, we would have a dependence on those digits).

Simplification yields $$T(n) = 12 \times 2^{\lfloor\log_3 n\rfloor} - \lfloor\log_3 n\rfloor^2 - 6 \lfloor\log_3 n\rfloor - 11.$$ With this exact formula it is now easy to see that the asymptotically dominant term is $$12 \times 2^{\lfloor\log_3 n\rfloor} \in \theta\left(2^{\log_3 n}\right) = \theta\left(3^{\log_3 2\log_3 n}\right) = \theta\left(n^{\log_3 2}\right).$$

There is a similar but slightly more advanced calculation at this MSE link and additional material is at this other MSE link.

| cite | improve this answer | |
$\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.