# Can we apply the Master Theorem to the following recurrence?

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?

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