Question

Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity \(\Theta(n)\)?

• A. \(T(n) = T(n-1) + 1, \quad T(1) = 1\)
• B. \(T(n) = 2T\left(\dfrac{n}{2}\right) + 1, \quad T(1) = 1\)
• C. \(T(n) = 2T\left(\dfrac{n}{2}\right) + n, \quad T(1) = 1\)
• D. \(T(n) = T(n-1) + n, \quad T(1) = 1\)

Hint:

Use the Master Theorem or expand each recurrence directly, then compare the resulting closed form against n, n log n, and n squared growth rates.

Answer 1

The Correct Option is A, B

Step 1: What we are hunting for.
We want recurrences whose closed form grows in direct proportion to $n$, that is $\Theta(n)$. The quickest way to test each one is to write out the first few terms or draw the recursion tree and see what total work comes out.

Step 2: Option (A), a chain that adds a constant.
$T(n) = T(n-1) + 1$ ticks down by one call at a time, adding $1$ unit of work each tick, starting from $T(1)=1$. There are $n-1$ ticks before we land on $T(1)$, so the total work is $1 + (n-1) = n$. That is exactly $\Theta(n)$, so (A) is in.

Step 3: Option (B), a splitting tree with tiny work per node.
$T(n) = 2T(n/2) + 1$ splits into two half sized calls plus $1$ unit of work at the current level. Picture the recursion tree: level $0$ has $1$ node doing $1$ unit, level $1$ has $2$ nodes doing $1$ unit each (total $2$), level $2$ has $4$ nodes (total $4$), and so on for $\log_2 n$ levels. Summing this geometric series gives about $2n$, which is still $\Theta(n)$. So (B) is in too.

Step 4: Option (C), the same split but with linear work per level.
$T(n) = 2T(n/2) + n$ looks similar to (B), but now each level does $n$ units of total work (it does not shrink), and there are $\log_2 n$ levels. Total work is $n \log_2 n$, which grows faster than plain $n$. So (C) is out. This is the familiar merge sort time.

Step 5: Option (D), a chain that adds a growing amount.
$T(n) = T(n-1) + n$ adds $n$ at the top, then $n-1$, then $n-2$, down to $1$. That sum is $\dfrac{n(n+1)}{2}$, which is $\Theta(n^2)$, not linear. So (D) is out.

Step 6: Collect the answers.
Only the chain with constant added work (A) and the halving tree with constant added work (B) grow as $\Theta(n)$.
\[ \boxed{\text{(A) and (B)}} \]