Solving recurrence relation using Master Method

Question

How to solve following recurrence relation?? $T(2n) = T(2n-20) + n.$

And if there is any other way despite Master's method to do this simpler way, what is it?

Answer 1

Let us assume WLOG that $n\equiv 1 \pmod{10}$, i.e. $n=10k+1$ for some nonnegative integer $k$. Then if $k\geqslant 1$,

\begin{align} T(n) &= \sum_{j=0}^k T(10(k-j)+1) + 10(k-j)\\ &= T(1) + \sum_{j=0}^k 10(k-j)\\ &= T(1) + 10\sum_{j=1}^k j\\ &= T(1) + 5k(k+1)\\ &= T(1) + 5\left(\frac{n-1}{10}\right)\left(\frac{n}{10}\right)\\ &= T(1) + \frac{n(n-1)}{50}, \end{align} so that $T(n)\in\Theta(n^2)$.

Answer 2

The master theorem isn't a good theorem to apply in this case, it's power comes from situations where the input size is reduced by a constant fraction (not decreased by a constant amount).

In this case, $$ T(n)=T(n-10)+n. $$ Then, $$ T(n-10)=T(n-20)+(n-10) $$ Similarly, $$ T(n-20)=T(n-30)+(n-20). $$ Therefore, $$ T(n)=T(n-10)+n=T(n-20)+[n+(n-10)]=T(n-30)+[n+(n-10)+(n-20)]=\cdots=\sum_{i=1}^{n/10}(n-10(i-1)) $$ (You will need appropriate ceiling/floor functions when $n$ is not a multiple of 10. The final sum should be proved with induction.)

Answer 3

Michael Burr's answer was first and is correct. Here is another way of explaining it using the technique of telescoping series. For every $n \in \{0, 1, 2, 3, \ldots\}$ we have: $$ T(n) - T(n-10) = n $$ Fix an integer $k \geq 1$. Writing this equation for $n\in\{10, 20, 30, ..., 10k\}$ gives: \begin{align} &\underbrace{T(10)}-T(0) &= 10\\ &T(20)-\underbrace{T(10)} &= 20 \\ &T(30)-T(20) &= 30\\ &T(40)-T(30) &= 40\\ &... &= ...\\ &T(10k) - T(10(k-1)) &= 10k \end{align} Summing all of these and noticing the cancellations on the left-hand-side (called telescoping sums, see the example terms that cancel that are underlined with braces above) gives: \begin{align} T(10k) - T(0) &= 10 + 20 + 30 + 40 + ... + 10k \\ &= 10\sum_{i=1}^k i \\ &= 5k(k+1) \end{align} So, a given initial condition $T(0)$ generates $T(10k)$ by: $$ \boxed{T(10k) = T(0) + 5k(k+1) \quad k \in \{1, 2, 3, ...\}} $$

In a similar way, you can show that an initial condition for $T(r)$ for $r \in \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ generates $T(10k+r)$.