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.