The relation t(n)=t(n-1)+n describes a common recurrence pattern in algorithm analysis, where the current term depends on the previous term plus the current index. This formulation captures how work accumulates step by step as input size grows.
Understanding how this recurrence behaves helps estimate running time and compare candidate algorithms in computer science and discrete mathematics contexts.
| Term Index | Recurrence | Expanded Value | Closed Form |
|---|---|---|---|
| t(1) | Base | 1 | 1 |
| t(2) | t(1)+2 | 1+2 | 3 |
| t(3) | t(2)+3 | 1+2+3 | 6 |
| t(4) | t(3)+4 | 1+2+3+4 | 10 |
| t(n) | t(n-1)+n | 1+2+...+n | n(n+1)/2 |
Recursive Expansion of t(n)=t(n-1)+n
Recursive expansion involves repeatedly substituting the recurrence until a clear pattern emerges. Starting from t(n), you replace each t(k) with t(k-1)+k until you reach the base case, revealing the sum of integers up to n.
This step-by-step substitution shows how the runtime accumulates across levels and highlights the arithmetic progression hidden in the relation.
Closed Form Derivation
By expanding t(n)=t(n-1)+n repeatedly, the expression simplifies to the sum of the first n natural numbers. This sum is well known and leads directly to the closed form n(n+1)/2.
The closed form allows constant-time evaluation for any n, avoiding the need for repeated recursion and making cost predictions straightforward.
Time Complexity and Growth Rate
The growth rate of t(n)=t(n-1)+n is quadratic, because the closed form is a degree two polynomial. As n increases, the runtime increases proportionally to n squared, dominated by the n^2 term.
In algorithm analysis, this behavior classifies the recurrence as Theta(n^2), indicating that doubling the input roughly quadruples the work.
Practical Implications for Algorithms
Many nested loop patterns generate this exact recurrence, especially when the inner loop depends linearly on the outer index. Recognizing this structure helps quickly estimate performance without detailed tracing.
Developers use this insight to anticipate bottlenecks and decide when to apply optimization techniques such as loop unrolling or mathematical simplifications.
Key Takeaways for Using t(n)=t(n-1)+n Effectively
- Recognize the pattern in nested loops where the inner bound depends on the outer index.
- Use the closed form n(n+1)/2 to evaluate costs without recursive expansion.
- Classify the growth as quadratic, guiding decisions when optimizing algorithms.
- Apply substitution or iteration methods to verify the closed form during analysis.
FAQ
Reader questions
How do I compute t(5) using the recurrence t(n)=t(n-1)+n with t(1)=1?
You expand stepwise: t(2)=3, t(3)=6, t(4)=10, t(5)=15, matching the sum 1+2+3+4+5.
What does the closed form n(n+1)/2 represent in this recurrence?
It provides a direct formula for the nth term, eliminating recursion and letting you compute the value in constant time.
Why is the time complexity Theta(n^2) for t(n)=t(n-1)+n?
The total work grows proportionally to the sum of the first n integers, which scales quadratically with n.
Can this recurrence appear in divide-and-conquer algorithms?
It can appear in specific unbalanced divide steps where subproblem reduction is linear and each level does work proportional to the index.