1

As per the title, I'm having some trouble to solve the recurrence equation

Edited

$$ T(N) = 2T \left(\left\lceil \frac{N+1}{2} \right\rceil\right) + 2T \left(\left\lfloor \frac{N+1}{2} \right\rfloor\right)$$ which is true for $N > 4$. I have two base cases, $T(3) = 6$ and $T(4) = 18$, but I'm stuck on how to proceed.

tigerjack
  • 93
  • Your base cases are contradictory. $T(3)=4T(2)$ and $T(4)=4T(2)$ so $T(3)=T(4)$ but this is not true. – Peter Foreman Mar 25 '19 at 21:20
  • 1
    Yeah, sorry it's fine now. – Peter Foreman Mar 25 '19 at 22:25
  • 2
    You mentioned $n^2 \ln n$, are you interested in the asymptotic behavior of $T(n)$? It is in fact $\Theta(n^2)$ by the master theorem. – Maxim Mar 27 '19 at 21:48
  • @Maxim thanks, it is surely better than nothing. But it could be great to also show the exact solution (constants throws in) or at least an approximation of it. Of course I'm also interested in the explanation (which in the case of master theorem is obvious). – tigerjack Mar 28 '19 at 06:41

1 Answers1

3

For the simplicity put $T(n)=6S(n)$ for each $n$. Then the sequence $S$ satisfies the same recurrence relation. A computed graph of the function $S$ suggests that it is piecewise linear with bends at $n=2^k+1$ and $2^k+2^{k-1}+1$. Indeed, by induction we can show that $S(2^k+1)=4^{k-1}$ and $S(2^k+2^{k-1}+1)=3\cdot 4^{k-1}$ for each $k\ge 1$. Also by induction we can show that between these points $S$ is linear, that is $$S(2^k+\lambda 2^{k-1}+1)=(1+2\lambda)4^{k-1}$$ and $$S(2^k+2^{k-1}+\lambda 2^{k-1}+1)=(3+\lambda)4^{k-1}$$ for each integer $2^{k-1}\lambda$ between $0$ and $2^{k-1}$. The found form of the function $S$ easily implies bounds $\frac {1}4\le\tfrac{S(n)}{ (n-1)^2}\le \frac 13$ (and $\tfrac 32(n−1)^2\le T(n)\le 2(n−1)^2$), for each $n\ge 3$.

Alex Ravsky
  • 90,434
  • 1
    Sorry for the late response. Thanks for your help, I'm trying to understand your steps. Anyhow, how could one derive the asymptotic behaviour from this? – tigerjack Apr 01 '19 at 15:54
  • Giving therefore $\frac{3}{2}(n-1)^2 \leq T(n) \leq 2(n-1)^2$, am I right? – tigerjack Apr 03 '19 at 08:34
  • Well, I couldn't hope for a better bound!!! I'm still trying to figure out your method, but anyhow many thanks for your help. Would you add the last comments in your answer? – tigerjack Apr 03 '19 at 08:40
  • Thanks again for the help. – tigerjack Apr 03 '19 at 08:48