0
$\begingroup$

I have divide and conquer problem and below is the recurrence relation for it $$\begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\ t(n) &= 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),&\text{ for }a = 8\\ O(n^2 \log(n)),&\text{ for }a = 16\\ O(n^5/2),&\text{ for }a=32 \end{cases}$$

Do these solution always apply if $n$ is not power of $4$ and how can I justify it?

$\endgroup$
1
  • $\begingroup$ Is the last case n^(5/2)? $\endgroup$ – gnasher729 Mar 23 at 14:23
0
$\begingroup$

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 < n < 4^(k+1) is between t(4^k) and t(4^(k+1)).

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