Question

Which of the following can be recurrence relation(s) corresponding to an algorithm
with time complexity Θ(𝑛)?

• A. 𝑇(𝑛) = 𝑇(𝑛−1) + 1, 𝑇(1) = 1
• B. \(T(n)=2T(n/2)+1,\quad T(1)=1\)
• C. \(T(n)=2T(n/2)+n,\quad T(1)=1\)
• D. 𝑇(𝑛) = 𝑇(𝑛−1) + 𝑛, 𝑇(1) = 1

Hint:

Solve each recurrence using unrolling or the Master theorem; only recurrences whose total work sums to a linear function of n qualify as Theta(n).

Answer 1

The Correct Option is A, B

The fastest way through this problem is to recognize each recurrence's shape rather than solving from scratch. \(T(n) = T(n-1) + 1\) does a constant amount of work at each of \(n\) levels of recursion, so the total work is linear, giving \(\Theta(n)\). For \(T(n) = 2T(n/2) + 1\), apply the Master theorem: the recursion tree has \(\log_2 n\) levels, and because the extra work per call is only a constant, with the total dominated by the \(\Theta(n)\) leaves, the total is \(\Theta(n)\) as well. Contrast this with \(T(n) = 2T(n/2) + n\), where linear work is done at every level of a tree with \(\log n\) levels, so the total becomes \(\Theta(n \log n)\), not linear. Similarly \(T(n) = T(n-1) + n\) adds a growing amount of work, \(n, n-1, n-2\) and so on, at each of \(n\) steps, summing to \(\Theta(n^2)\). So only the first two recurrences, options A and B, describe an algorithm with time complexity \(\Theta(n)\).