Multiple choice

Directions: Find the time complexities of the following question.

T(n)=2T(n/2)+n/logn

  1. O(n2)

  2. O(n log n)

  3. O(n)

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

The recursion tree has log n levels, each contributing n/log(n/2^i). Level 0: n/log n, Level 1: n/log(n/2), ..., Level log n: O(log n). Using the integral approximation, the sum of n/log(n/2^i) for i=0 to log n is O(n log log n). This is because we're essentially summing 1/log(x) which gives the log log factor.

Keep practicing — related questions