Divide and conquer recurrence relation I have divide and conquer problem and below is the recurrence relation for it
$$\begin{align}t (n) &amp;= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\
t(n) &amp;= a\cdot t (n/4) + O(n^2)
\end{align}$$
I solved this recurrence for different values of $a$. These are the solutions below
$$ =\begin{cases}O(n^2),&amp;\text{ for }a = 8\\
O(n^2 \log(n)),&amp;\text{ for }a = 16\\
O(n^5/2),&amp;\text{ for }a=32
\end{cases}$$
Do these solution always apply if $n$ is not power of $4$ and how can I justify it?
You need to define first where the recursion ends. And what t(n/4) means if n is not a multiple of 4.
The likely outcome will be that t(n) for 4^k &lt; n &lt; 4^(k+1) is between t(4^k) and t(4^(k+1)).