MHB Confusion with variables when solving a recurrence equation

[JimmyK]

If I have a recurrence equation of the following form:

$$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.

 

[Sudharaka]

If I have a recurrence equation of the following form:

$$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.

Hi marobin, :)

It seems that your recurrence relation is in fact a constant sequence since \(T(n) = T(km)=a\mbox{ for }m\geq 1\).

Kind Regards,
Sudharaka.