The asymptotic upper bound solution of the recurrence relation given by \(T(n)…
2017
The asymptotic upper bound solution of the recurrence relation given by
\(T(n) = 2T \left( \frac{n}{2} \right) +\frac{n}{\lg \: n}\)
- A.
\(O(n^2)\) - B.
\(O(n \:\lg \: n )\) - C.
\(O(n \:\lg \:\lg \: n)\) - D.
\(O(\lg \:\lg \: n)\)
Attempted by 54 students.
Show answer & explanation
Correct answer: C
Answer: Theta(n log log n).
Derivation using a recursion tree:
At level j (root is j = 0) there are 2^j subproblems, each of size n/2^j. The nonrecursive work per subproblem is (n/2^j)/log(n/2^j).
Total work at level j: 2^j * (n/2^j)/log(n/2^j) = n / (log n - j).
There are about L = log_2 n levels, so the total internal work is n * sum_{j=0}^{L-1} 1/(log n - j) = n * sum_{k=1}^{log n} 1/k = n * H_{log n}.
Using H_m = Theta(log m) gives total work Theta(n log log n). The leaf-level cost is Theta(n) and is dominated by n log log n for large n.
Therefore, T(n) = Theta(n log log n).