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!
Well my first guess would be that the "???" equals
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.