# Math Help - Recurrence relation

1. ## Recurrence relation

Hi, I try to solve this relation
$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.

2. Originally Posted by liberty
Hi, I try to solve this relation
$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.

Something seems to be lacking here: first, I pressume you know/you're given the few first elements $T(0), T(1),...$, and also: the given recurrence relation only works for even indexes: what happens with odd ones?

Tonio

3. Hi Tonio,correct.
But we can skip this assuming that n is a power of 2. or we can solve this
$
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 $O(n^{\log n} )$