Multiple choice

Directions: Find the time complexities of the following question.

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

  1. O(n2)

  2. O(n log n)

  3. O(n)

  4. O(log n)
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

This recurrence decreases the problem size by 1 each step while adding 1/n. Expanding gives T(n) = T(0) + 1/1 + 1/2 + 1/3 + ... + 1/n. This sum is the harmonic series H_n, which grows logarithmically. The n² and n options are incorrect because the terms 1/n get progressively smaller, and n log n would require linearly growing terms.

Keep practicing — related questions