Search code examples
recursiondata-structuresrecurrence

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.