Can we apply the Master Theorem to the following recurrence?

Question

Our recurrence is

$$ T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\ 1 & \text{if $n=1.$} \end{cases} $$

I have identified $a = 1 > 0$, and $b = 2 > 1$. I am having trouble identifying the $c$ (for $n^{c}$ in $f(n) =(\log(n))^{2}$. The best I could break it down to was $(\log(n))^{2} = \log(n)^{1}*\log(n)^{1}$, which doesn't seem to be the form we are looking for, as $\log(n) \ne n$. Also, how do we take the floor operator into account?

If it follows that we can't apply the Master Theorem (which seems to be the case), what is the culprit?

Answer 1

So, we have that $f(n) = O(n^c \log^k(n)) = O(n^0 \log^2(n))$; and since $log_b(a) = log_2(1) = 0 = c$, we are in the 2nd case of the Master's theorem (work to divide the problems is comparable to the work on subproblems (wiki)); thus, applying the theorem, we get $T(n) = \Theta(log^3(n))$.

On the floor operation, I don't know what is the cleanest way of solving it; one way could be to prove it for $n = 2^m$, and then extend to all $\mathbf{N}$ by monotonicity.

We can also calculate $T(n)$ directly:

$$T(n) = T(n/2) + log^2(n) = \sum_{j=0}^{log(n)} log^2(2^j) = log^2(2) \sum_{j = 0}^{log(n)} j^2 = \theta(log^3(n))$$

Answer 2

Let $S(n) := T(2^n)$, then $S(0) = 1$ and $S(n) = S(n-1) + n^2$ for $n ≥ 1$. $S(n)$ is therefore just a straightforward sum, $1 + sum(n'^2)$ for $1 ≤ n' ≤ n$, roughly $n^3 / 3$.

So $T(n)$ = roughly $(\log n)^3 / 3$ if n is a power of two, you can find the exact value. If n is not a power of two then $T(n^k) ≤ T(n) ≤ T(2 \cdot 2^k)$ for two powers of two around n. You can get it a bit more precise: If you calculate $T(c \cdot 2^k)$ for $1 ≤ c ≤ 2$, then you will repeatedly have $(\log c + n')^2$ instead of $(n')^2$. Your sum will be about $T(c \cdot 2^k) ≈ \log c \cdot k + (\log k)^3 / 3$ which will be about $(\log n)^3$ for $n = c \cdot 2^k$. (Obviously find a more precise formula for the sum of n^2).