Time Complexity Analysis with Recurrence Relations — Read

Opening the reading…

A recurrence must include the work outside the recursive call

Consider work(4). At n = 4, the function executes its loop body four times, then makes one recursive call to work(3). The recursive call has its own cost, so the total cost of work(4) is not just the cost of making one call. It is the four local units plus everything done by work(3).

Let T(n) represent the modeled cost of work(n). For every positive n, the loop contributes n units and the recursive call contributes T(n - 1). Therefore, the recurrence is T(n) = T(n - 1) + n. Counting only the recursive calls would record one call at each level, but it would miss the loop executions at those levels.

TEXTThe recursive term and the local-work term both belong in the recurrence.

work(4)
= 4 local loop units + cost of work(3)
= 4 + T(3)

T(n) = T(n - 1) + n

CHECKPOINT 1Not answered

Which recurrence correctly models the cost of work(n), where the loop runs n times before one call to work(n - 1)?

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

The base case anchors the recurrence with a concrete cost

When work reaches work(0), it reaches the base case and makes no further recursive call. Under the stated cost model, that base-case event costs one unit, so T(0) = 1. This value is the point where the recurrence stops.

If you wrote T(0) as an unspecified value such as c, the expansion would end with c instead of a number. You could still conclude the same asymptotic class, because one constant does not change the growth rate. The concrete base cost is needed when you want the modeled total for a particular input, such as work(4).

Expanding the recurrence exposes all work done by work(4)

Start with T(4) = T(3) + 4. The 4 is the loop work at the call level where n equals 4. Replace T(3) using the same recurrence, then continue until T(0), where the base cost is known.

TEXTEach number comes from the loop at one call level, except the first 1, which is T(0).

T(4) = T(3) + 4
     = (T(2) + 3) + 4
     = ((T(1) + 2) + 3) + 4
     = (((T(0) + 1) + 2) + 3) + 4
     = 1 + 1 + 2 + 3 + 4
     = 11

Every level adds local work before the recurrence reaches its base cost.

CHECKPOINT 2Not answered

Type the fully expanded numeric expression for T(4), including the base-case cost.

Checkpoints are not graded. They are here so you catch yourself before the quiz does — stuck, ask the tutor on the right.

One recursive call per level can still produce quadratic time

For a general positive n, expanding the same recurrence gives T(n) = n + (n - 1) + (n - 2) + ... + 1 + T(0). Since T(0) = 1, this is 1 + 1 + 2 + ... + n. The call chain has only n non-base levels, but the local work grows from 1 to n across those levels.

The sum 1 + 2 + ... + n is a triangular sum, equal to n(n + 1) / 2. Adding the constant base cost gives T(n) = n(n + 1) / 2 + 1, which is Theta(n^2). The function is not linear merely because it makes one recursive call per level. Linear call depth combined with growing local work produces quadratic total time.