Hi, I try to solve this relation
$\displaystyle T(n) = 2n + 2nT(n/2)$, I try with substitutions but then i must calculate a sum that i find it difficult, so i wonder if there is an other way to go.
Any ideas? Thanks in advance.
Hi Tonio,correct.
But we can skip this assuming that n is a power of 2. or we can solve this
$\displaystyle
T(n) = 2n + 2nT(\left\lfloor {\frac{n}{2}} \right\rfloor )$
T(1) = 1.
I would be glad with an approximate answer, for example like that $\displaystyle O(n^{\log n} )$