CoursifyCoursify

Solving the Recurrence T(n)=T(n−1)+nT(n)=T(n-1)+n by Substitution Method

Solving the Recurrence T(n)=T(n−1)+nT(n)=T(n-1)+n by Substitution Method

Verified Sources
May 25, 2026

A recurrence is a common way to describe the running time of recursive or incremental algorithms. In this problem, the number of basic operations is defined by

T(n)=T(n−1)+n,T(1)=1T(n)=T(n-1)+n,\qquad T(1)=1

This is a decrease-by-one recurrence: each step reduces the problem size by 1 and adds a linear amount of work, namely nn.2 The substitution method solves it by repeatedly replacing the smaller term T(n−1)T(n-1) with its own recurrence until the base case is reached.2

The key idea is that the recurrence unfolds into a sum of the first nn natural numbers, which has closed form

1+2+⋯+n=n(n+1)2.1+2+\cdots+n=\frac{n(n+1)}{2}.

Therefore, we should expect quadratic growth, i.e. Theta notation Θ(n2)\Theta(n^2).2

Footnotes

  1. Time Complexity Analysis of Recursive Functions - GeeksforGeeks - Overview of recurrence-solving methods, including substitution. ↩ ↩2

  2. SolvingRecurrences - Yale University - Notes explaining asymptotic solutions and the form T(n)=T(n−1)+f(n)T(n)=T(n-1)+f(n). ↩ ↩2

  3. Easy: Solve T(n)=T(n-1)+n by Iteration Method - Stack Overflow - Shows repeated expansion pattern leading to the summation. ↩

  4. 2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2 - YouTube - Demonstrates expansion of this exact recurrence and concludes quadratic growth. ↩

Substitution Method to Solve Recurrence Relation of Time

Core Observation

Because each recursive expansion adds the next integer, the recurrence accumulates the sum 1+2+⋯+n1+2+\cdots+n, which grows quadratically.2

Footnotes

  1. Time Complexity Analysis of Recursive Functions - GeeksforGeeks - Overview of recurrence-solving methods, including substitution. ↩

  2. 2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2 - YouTube - Demonstrates expansion of this exact recurrence and concludes quadratic growth. ↩

Solving $T(n)=T(n-1)+n$ Using Substitution

  1. 1
    Step 1

    Start with T(n)=T(n−1)+nT(n)=T(n-1)+n and the base case T(1)=1T(1)=1.

    Footnotes

    1. Time Complexity Analysis of Recursive Functions - GeeksforGeeks - Overview of recurrence-solving methods, including substitution. ↩

  2. 2
    Step 2

    Replace T(n−1)T(n-1) using the same rule: T(n−1)=T(n−2)+(n−1)T(n-1)=T(n-2)+(n-1). Then T(n)=T(n−2)+(n−1)+nT(n)=T(n-2)+(n-1)+n.2

    Footnotes

    1. Time Complexity Analysis of Recursive Functions - GeeksforGeeks - Overview of recurrence-solving methods, including substitution. ↩

    2. Easy: Solve T(n)=T(n-1)+n by Iteration Method - Stack Overflow - Shows repeated expansion pattern leading to the summation. ↩

  3. 3
    Step 3

    Expand again: T(n−2)=T(n−3)+(n−2)T(n-2)=T(n-3)+(n-2), so T(n)=T(n−3)+(n−2)+(n−1)+nT(n)=T(n-3)+(n-2)+(n-1)+n. A pattern now appears.2

    Footnotes

    1. Time Complexity Analysis of Recursive Functions - GeeksforGeeks - Overview of recurrence-solving methods, including substitution. ↩

    2. Easy: Solve T(n)=T(n-1)+n by Iteration Method - Stack Overflow - Shows repeated expansion pattern leading to the summation. ↩

  4. 4
    Step 4

    After kk expansions, T(n)=T(n−k)+∑i=0k−1(n−i)T(n)=T(n-k)+\sum_{i=0}^{k-1}(n-i). Equivalently, T(n)=T(n−k)+(n−k+1)+(n−k+2)+⋯+nT(n)=T(n-k)+(n-k+1)+(n-k+2)+\cdots+n.

    Footnotes

    1. Easy: Solve T(n)=T(n-1)+n by Iteration Method - Stack Overflow - Shows repeated expansion pattern leading to the summation. ↩

  5. 5
    Step 5

    Set n−k=1n-k=1, so k=n−1k=n-1. Then the recurrence becomes T(n)=T(1)+2+3+⋯+nT(n)=T(1)+2+3+\cdots+n.

    Footnotes

    1. Easy: Solve T(n)=T(n-1)+n by Iteration Method - Stack Overflow - Shows repeated expansion pattern leading to the summation. ↩

  6. 6
    Step 6

    Since T(1)=1T(1)=1, we get T(n)=1+2+3+⋯+nT(n)=1+2+3+\cdots+n.

    Footnotes

    1. Time Complexity Analysis of Recursive Functions - GeeksforGeeks - Overview of recurrence-solving methods, including substitution. ↩

  7. 7
    Step 7

    The sum of the first nn natural numbers is n(n+1)2\frac{n(n+1)}{2}. Therefore T(n)=n(n+1)2T(n)=\frac{n(n+1)}{2}.

    Footnotes

    1. 2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2 - YouTube - Demonstrates expansion of this exact recurrence and concludes quadratic growth. ↩

  8. 8
    Step 8

    The dominant term is 12n2\frac{1}{2}n^2, so the time complexity is Θ(n2)\Theta(n^2).2

    Footnotes

    1. SolvingRecurrences - Yale University - Notes explaining asymptotic solutions and the form T(n)=T(n−1)+f(n)T(n)=T(n-1)+f(n). ↩

    2. 2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2 - YouTube - Demonstrates expansion of this exact recurrence and concludes quadratic growth. ↩

Closed-Form Derivation

Using back substitution, we obtain

T(n)=T(n−1)+n=(T(n−2)+(n−1))+n=T(n−2)+(n−1)+n=(T(n−3)+(n−2))+(n−1)+n=T(n−3)+(n−2)+(n−1)+n  ⋮=T(1)+2+3+⋯+n.\begin{aligned} T(n) &= T(n-1)+n \\ &= \bigl(T(n-2)+(n-1)\bigr)+n \\ &= T(n-2)+(n-1)+n \\ &= \bigl(T(n-3)+(n-2)\bigr)+(n-1)+n \\ &= T(n-3)+(n-2)+(n-1)+n \\ &\ \ \vdots \\ &= T(1)+2+3+\cdots+n. \end{aligned}

Since T(1)=1T(1)=1,

T(n)=1+2+3+⋯+n.T(n)=1+2+3+\cdots+n.

Now apply the standard summation formula:

∑i=1ni=n(n+1)2.\sum_{i=1}^{n} i = \frac{n(n+1)}{2}.

Hence,

T(n)=n(n+1)2.T(n)=\frac{n(n+1)}{2}.

Expanding,

T(n)=12n2+12n.T(n)=\frac{1}{2}n^2+\frac{1}{2}n.

The dominant term is n2n^2, so

T(n)=Θ(n2).T(n)=\Theta(n^2).

This agrees with the general principle that recurrences of the form T(n)=T(n−1)+f(n)T(n)=T(n-1)+f(n) accumulate the total sum of f(i)f(i) over smaller inputs.2

Footnotes

  1. SolvingRecurrences - Yale University - Notes explaining asymptotic solutions and the form T(n)=T(n−1)+f(n)T(n)=T(n-1)+f(n). ↩

  2. Time Complexity Analysis of Recursive functions using Recurrence - UCF PDF - Academic notes on solving decrease-by-one recurrences through repeated substitution. ↩

Growth of T(n)=n(n+1)2T(n)=\frac{n(n+1)}{2}

Sample values illustrating quadratic growth

Why the Complexity is Θ(n2)\Theta(n^2)

In asymptotic analysis, constants and lower-order terms are ignored. For

T(n)=12n2+12n,T(n)=\frac{1}{2}n^2+\frac{1}{2}n,

the term 12n2\frac{1}{2}n^2 dominates as nn grows large. Therefore,

T(n)∈Θ(n2).T(n)\in \Theta(n^2).

This means:

  • it is not merely an upper bound like O(n2)O(n^2),
  • it is also a matching lower bound,
  • so the growth rate is tightly quadratic.2

A useful intuition is that the recurrence adds a cost of about nn at the top level, then n−1n-1, then n−2n-2, and so on down to 11. That staircase-shaped accumulation produces an area proportional to n2n^2.2

Footnotes

  1. SolvingRecurrences - Yale University - Notes explaining asymptotic solutions and the form T(n)=T(n−1)+f(n)T(n)=T(n-1)+f(n). ↩

  2. 2.1.2 Recurrence Relation (T(n)= T(n-1) + n) #2 - YouTube - Demonstrates expansion of this exact recurrence and concludes quadratic growth. ↩

  3. Time Complexity Analysis of Recursive Functions - GeeksforGeeks - Overview of recurrence-solving methods, including substitution. ↩

  4. Easy: Solve T(n)=T(n-1)+n by Iteration Method - Stack Overflow - Shows repeated expansion pattern leading to the summation. ↩

Exam Technique

For recurrences of the form T(n)=T(n−1)+f(n)T(n)=T(n-1)+f(n), try expanding until the base case and then convert the result into a summation. This often reveals the closed form quickly.

Footnotes

  1. Time Complexity Analysis of Recursive functions using Recurrence - UCF PDF - Academic notes on solving decrease-by-one recurrences through repeated substitution. ↩

1T(n)=T(n-1)+n
2    =T(n-2)+(n-1)+n
3    =...=T(1)+2+3+...+n
4    =1+2+3+...+n
5    =n(n+1)/2
6Therefore, T(n)=Θ(n^2).

Common Questions and Pitfalls

Common Mistake

Do not stop at T(n)=T(n−k)+knT(n)=T(n-k)+kn; that misses the decreasing terms (n−1),(n−2),...(n-1),(n-2),.... The correct expansion produces a sum, not just repeated copies of nn.

Footnotes

  1. Easy: Solve T(n)=T(n-1)+n by Iteration Method - Stack Overflow - Shows repeated expansion pattern leading to the summation. ↩

Final Answer

The recurrence

T(n)=T(n−1)+n,T(1)=1T(n)=T(n-1)+n,\qquad T(1)=1

solves to

T(n)=n(n+1)2.T(n)=\frac{n(n+1)}{2}.

Therefore, the algorithm performs a quadratic number of basic operations, and its time complexity is

Θ(n2).\boxed{\Theta(n^2)}.

Knowledge Check

Question 1 of 4
Q1Single choice

After one substitution, what does T(n)T(n) become?

Explore Related Topics

1

Mastering Recurrence Relations: The Substitution Method

The lesson shows how to solve the classic recurrence T(n)=2T(n/2)+nT(n)=2T(n/2)+n with the substitution method, using a recursion‑tree intuition to guess an O(nlog⁡n)O(n\log n) bound and then proving it by induction.

  • Each level of the recursion tree costs nn, and there are log⁡2n\log_2 n levels → total Θ(nlog⁡n)Θ(n\log n).
  • Inductive hypothesis: T(n)≤c nlog⁡2nT(n)\le c\,n\log_2 n for n≥n0n\ge n_0, which simplifies to c≥1c\ge1 in the induction step.
  • The base case must start at n0>1n_0>1 (e.g., n0=2n_0=2) because T(1)≤c⋅1log⁡21T(1)\le c\cdot1\log_2 1 is false.
  • Substitution offers rigorous proof, while recursion trees give quick guesses; the Master Theorem confirms T(n)=Θ(nlog⁡n)T(n)=Θ(n\log n).
2

Quick Sort Algorithm and Its Best-, Worst-, and Average-Case Time Complexities

Research more with Coursify
Chat with Kiro