Recurrence equation for $T(n)=4T(n/2)+cn$

Question

I'm trying to resolve this recurrence equation $T(n)=4T(\frac{n}{2})+cn$.

The solution I discovered online is $T(n)=\theta(n^2)$.

The steps I follow was these:
a) Create the tree of recurrence as this:

                     cn                       cost cn
         /       /       \       \
     c(n/2)   c(n/2)   c(n/2)  c(n/2)         cost 2cn
      //\\     //\\     //\\    //\\
c(n/2)^2   c(n/2)^2   c(n/2)^2  ... c(n/2)^2  cost 2^2cn
   ...        ...       ...     ...    ...
T(1) T(1) ... T(1) T(1)                       cost 2^icn

With $\log_2n$ expected level. So the longest path and calculation shall be $2^i\log_2cn$, now I think I can ignore the $2^i$ and got an $O(n\log n)$. That differs from the solution.

I tried to follow with the substitution method:
b) let's assume O(n\log n), $f(n) = dn\log_2n$ with d a constant greater than zero be more of our function, with the constant c set as the same value $d$.

$T(n) <= 4d\frac{n}{2}\log_2n+cn$
$T(n) <= 2dn\log_2n+cn$
$dn\log_2n <= 2dn\log_2n+cn$
$-dn\log_2n <= cn$
true for all $d>=\frac{c}{\log_2n}$

Where am I wrong?

Source of the solutions: a) That says shall be $n^2+2cn$: https://github.com/gzc/CLRS/blob/master/C04-Recurrences/4.2.md, point 4.2-3 b) WolframAlpha, that say is, is a $\theta$ of $n^2$ https://www.wolframalpha.com/input?i=g%28n%29%3D4g%28n%2F2%29

Answer 1

I'm not that familiar with the recursive tree method, but it seems that you only consider the longest path, when you should have calculated the total cost, which takes the form of a partial geometric series :
$$ \sum_{k=0}^{\log_2(n)}2^kcn = cn\frac{2^{\log_2(n)+1}-1}{2-1} = cn(2n-1) \sim n^2 $$ whence the desired result.

---

Addendum Here is an exact derivation of the solution.

The recurrence relation can be rewritten and simplified thanks to re-indexation, such that $a_n := T(2^n) = 4T(2^{n-1}) + 2^nc = 4a_{n-1} + 2^nc$. Now it is a first-order inhomogeneous linear recurrence relation.

The homogeneous solution is derived straightforwardly from $b_n = 4b_{n-1}$, which gives $b_n = 4^nb_0$, whereas the particular solution can be determined from the ansatz $2^n\alpha$, which leads to $\alpha = -c$ and, in fine, to the solution $a_n = 4^nb_0-2^nc$, with $b_0$ a constant.

Coming back to the initial problem, we find $T(n) = a_{\log_2(n)} = 4^{\log_2(n)}b_0-2^{\log_2(n)}c = b_0n^2+cn$, with $b_0 = T(1)-c$ due to the initial condition.

Answer 2

$T(n)=4T(n/2)+cn$

$ =4[4T(n/4)+cn/2]+cn$

$ =16T(n/4)+3cn$

$ =16[4T(n/8)+cn/4]+3cn$

$ =64T(n/8)+7cn$

$ =64[4T(n/16)+cn/8]+7cn$

$ =256T(n/16)+15cn$

......................

......................

After k substitutions:

$ =4^{k+1}T(n/2^{k+1})+(2^{k+1}-1)cn$

Putting $k=log(n)$ as after $log(n)$ steps the $T(n/2^k)$ converges to $T(1)$,

$ =4n^2T(1/2)+(2n-1)cn$

$ =n^2.c' + n(2n-1)c$

$ = ~ O(n^2)$

Answer 3

Rewrite $T(2n)=4T(n)+2cn$ and set $U(n)=\dfrac{4T(n)}{n}+\alpha \dfrac{2cn}n$

(this is motivated by this -> https://math.stackexchange.com/a/3002925/399263)

After substitution the $n$ gets to simplify and you have :

$U(2n)=\dfrac{4T(2n)}{2n}+2\alpha c=\dfrac{16T(n)+8cn}{2n}+2\alpha c=2U(n)+(4c-2\alpha c)$

We see that setting $\alpha=2$ gets rid of the constant term and simplifies the relation to $$U(2n)=2U(n)$$

Which solves to $U(n)=n\,U(1)$

( side note: $n=2^p$ and $V(p)=U(n)$ gives $V(p+1)=2V(p)\iff U(n)=V(p)=2^pV(0)=nV(0)=nU(1)$ )

Reporting in initial term gives $$T(n)=\frac 14n^2\,U(1)-cn=n^2\,T(1)+n(n-1)c=\mathcal O(n^2)$$