# Thread: Recurrence relation

1. ## Recurrence relation

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.

2. Originally Posted by liberty
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.

Something seems to be lacking here: first, I pressume you know/you're given the few first elements $\displaystyle 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
$\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} )$