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?


2 Answers 2


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))$$


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.