2.1.1 Recurrence Relation (T(n)= T(n-1) + 1) #1

Summary

The video demonstrates how to analyze a simple recursive function by tracing its calls, writing a recurrence relation, and solving it with back substitution.

1. Trace the recursive function

The example function receives n. If n > 0, it prints n and calls itself with n - 1. For an input of 3, the calls proceed as follows:

• test(3) prints 3, then calls test(2).
• test(2) prints 2, then calls test(1).
• test(1) prints 1, then calls test(0).
• test(0) does not satisfy the condition, so recursion stops.

Thus, the function prints n values and makes n + 1 calls, including the final call at zero.

2. Estimate the running time

The instructor treats the print operation as constant work per recursive call and ignores other constant-cost operations, such as checking the condition. Since there are n printing calls, the work grows linearly with n.

3. Write the recurrence

Let T(n) represent the running time:

• For n > 0: T(n) = T(n - 1) + 1
• At the base case n = 0: T(0) is a constant, represented as 1

The exact constant used for the base case or other fixed operations does not change the overall asymptotic result.

4. Solve by back substitution

Repeatedly substitute the recurrence into itself:

• T(n) = T(n - 1) + 1
• T(n) = T(n - 2) + 2
• T(n) = T(n - 3) + 3
• After k substitutions: T(n) = T(n - k) + k

Stop when the argument reaches the base case, so n - k = 0, meaning k = n. Then:

• T(n) = T(0) + n
• With T(0) = 1, T(n) = n + 1

The result is linear time: Θ(n) (and therefore also O(n) and Ω(n)).

Speakers and sources

• Abdul Bari — sole speaker and instructor, explaining the recursive function and its analysis.
• No other speakers or external sources are identified in the subtitles.