CUET PG 2026 — DSA PYQ

To solve the recurrence $T(n)=T(n-1)+\log n$, expand it recursively:

$$T(n)=T(n-1)+\log n$$

$$T(n)=T(n-2)+\log (n-1)+\log n$$

$$T(n)=T(n-3)+\log (n-2)+\log (n-1)+\log n$$

Continuing this process down to the base case $T(1)=O(1)$:

$$T(n)=\log 1+\log 2+\log 3+\cdots +\log n$$

Using the logarithm product rule ($\log a+\log b=\log (ab)$):

$$T(n)=\log (1\cdot 2\cdot 3\cdot \cdots \cdot n)=\log (n!)$$

By Stirling's Approximation, $\log (n!)=\Theta (n\log n)$.

Therefore, $T(n)=O(n\log n)$.

Correct Answer: (B) $O(n\log n)$