2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\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.