- Thread starter
- #1

#### ATroelstein

##### New member

- Jun 30, 2012

- 15

T(n) = T(ij) = m if j = 1, where m just denotes a constant

T(n) = T(ij) = T(i) + T(i(j-1)) + cn if j > 1

T(i) = m

T(2i) = m + m + c*2i = 2m + 2ci

T(3i) = m + 2m + 2ci + 3ci = 3m + 5ci

So it looks like the recurrence is:

$$T(n) = jm + (ci\sum_{k=1}^{j}k) - 1$$

At this point, I'm a bit lost as to what to do. It looks the summation at the end will result in j^2 if expanded out, but I need to show that it somehow equals n^2. Any explanation on how to continue with this would be appreciated.