Unroll the recurrence. Expanding repeatedly gives T(n)=T(n-2)+2= =T(0)+n. Conclude the complexity. With T(0) constant, T(n)= (n).

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

Coding

Recurrences

Easy

Solve

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

Hint 1

Each recursive call reduces the problem size by only 1 unit while doing constant work.

Hint 2

Unroll the recurrence to count the number of calls before reaching the base case.

Show worked solution

1. Unroll the recurrence
Expanding repeatedly gives $T (n) = T (n - 2) + 2 = \dots = T (0) + n$ .
2. Conclude the complexity
With $T (0)$ constant, $T (n) = Θ (n)$ .

Answer: O(n)

1. Unroll the recurrence