# Recurrence relation: T(n) = n*T(n/2)

I’ve been trying to solve this problem but I am stuck at the last bit and my University lecturer doesn’t really want to help me 🙂

T(1) = 1

T(n) = n*T(n/2)

``````T(n/2) = n/2 * T(n/4);
T(n/4) = n/4 * T(n/8);
T(n/8) = n/8 * T(n/16);

The four forms:
1) T(n) = n * T(n/2);         k = 1
2) T(n) = (n^2)/2 * T(n/4);   k = 2
3) T(n) = (n^3)/8 * T(n/8);   k = 3
4) T(n) = (n^3)/64 * T(n/16); k = 4

T(n) = (n^k)/??? * T(n/k^2)
``````

I can see the relationship, but I don’t quite know what the ??? equals, nor how to continue. Honestly, any help would be greatly appreciated. Thank you!

### >Solution :

Well my first guess would be that the "???" equals
`2^(k-1)`,
because then the sequence would be like, 2^1-1=1, 2^2-1=2 and so on…

Then you would have the recurrence relation as follows:

``````T(n)=(n^k)/(2^(k-1)) * T(n/k^2)
``````

Then you can prove by induction that this holds for any n. And I assume that since this an algorithm-related question, this would give you a bound for the running time.