Multiple choice

Directions: Find the time complexities of the following question.

T(n)=T(n/2)+T(n/4)+T(n/8)+n

  1. O(n2)

  2. O(n log n)

  3. O(n)

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

At each level, the total work is n + n/2 + n/4 + n/8 + ... (sum of T(n/2), T(n/4), T(n/8) contributions) plus the constant n at the root. The sum n(1 + 1/2 + 1/4 + 1/8 + ...) converges to 2n = O(n). The O(n²) option would require quadratic growth at each level, and O(log n) ignores the linear work at each node.

Keep practicing — related questions