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.