- Thread starter
- #1

$$T(n) = T(km) = a, m = 1$$

$$T(n) = T(km) = T(k) + T(k(m-1)) + cn, m > 1$$

Where a is simply a constant, and k is an integer constant > 0.

Now I begin substituting to find the pattern:

$$T(k) = a$$

$$T(2k) = a + [a] + c2k$$

$$T(2k) = 2a + 2ck$$

$$T(3k) = a + [2a + 2ck] + c3k$$

$$T(3k) = T(3k) = 3a + 5ck$$

$$T(4k) = a + [3a + 5ck] + c4k$$

$$T(4k) = 4a + 9ck$$

So it looks like the solution is:

$$T(n) = T(mk) = ma + ((\sum\limits_{i=1}^mi)-1)ck$$

$$T(n) = T(mk) = ma + (\frac{m}{2}(m+1)-1)ck$$

Now what I want to do is show that $$T(n) = \Theta(n^{2})$$

I can see in my solution that expanding it out, we end with a leading term of: $$m^{2}$$

Now my problem is, I have myself completely confused due to the variable names. T(n) = T(mk) and then the leading term is m^2, but I want to show that T(n) = Theta(n^2) and I don't think I've fully shown that because while m is dependent on n, it's not n. Any explanation of how I go about relating the two would be appreciated.