Multiple choice

Directions: Find the time complexities of the following question.

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

  1. O(n2)

  2. O(n log n)

  3. O(n)

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

This recurrence adds log n at each of n steps. Summing log 1 + log 2 + ... + log n = log(n!) ≈ n log n - n + O(log n) by Stirling's approximation. Therefore T(n) = O(n log n). The O(n) option would require constant work per step, and O(n²) would require linearly growing work.

Keep practicing — related questions