edited by
5,017 views
3 votes
3 votes

The asymptotic upper bound solution of the recurrence relation given by $T(n) = 2T \left( \frac{n}{2} \right) +\frac{n}{\lg \: n}$ is

  1. $O(n^2)$
  2. $O(n \:\lg \: n )$
  3. $O(n \:\lg \:\lg \: n)$
  4. $O(\lg \:\lg \: n)$
edited by

11 Answers

Best answer
3 votes
3 votes

Option C) by master's theorem. A = 2, B = 2 and K =1 and P = -1. 

As a = bk and p = -1

answer is  O (nlog22 log log n) = O(n log log n)

selected by
5 votes
5 votes

$$T(n)=2T\left(\frac{n}{2}\right)+\frac{n}{\lg n}$$

For Master theorem, $a = 2, b = 2, n^{\log _b a} = n$. $f(n) = \frac{n}{\lg n}$. We cannot say $f(n) = O(n^{\log_b a - \epsilon})$, as the difference between $n$ and $\frac{n}{\lg n}$ is not polynomial. So, we cannot apply Master theorem. So, trying substitution. Since, we have a lg term, we can try all powers of 2.

$T(1) = 1$, assuming.

$T(2) = 2T(1) + \frac{2}{\lg 2} = 4$

$T(4) = 8 + 2 = 10$

$T(8) = 20 + \frac{8}{3} = 22.66$

$T(16) = 45.3 + 4 = 49.3$

$T(32) = 98.6 + 6.4 = 105$

$T(64) = 210 + 10.6 = 220.6$

Not able to reach a conclusion. We can see that the recurrence is between case 1 and case 2 of Master theorem. So, it is $\Omega \left(n\right)$ and $O\left(n \lg n\right)$. So, lets solve the recurrence directly.

$T(n)=2T\left(\frac{n}{2}\right)+\frac{n}{\lg n}$

$= 2^2 T\left(\frac{n}{4}\right)+\frac{n}{\lg n - 1} + \frac{n}{\lg n}$

$\dots$

$= 2^{\lg n} T(1) + \frac{n}{1} +  \frac{n}{2} +  \dots +  \frac{n}{\lg n}$

$= n + n \left( \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{\lg n}\right)$

$=n + n \left(\lg \lg n + \gamma \right)\\= \Theta\left(n \lg \lg n\right)$

The sum of $\lg n$ terms in HP approximated to $\lg \lg n +\gamma$ where $\gamma$ is Euler Mascheroni constant. 

Ref: https://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant

edited by
5 votes
5 votes
1 votes
1 votes

Option C)

MASTER THEOREM

A = 2, B = 2 and K =1 and P = -1. 

As a = bk and p = -1

answer is  O (nlog22 log log n) = O(n log log n)

CASE 2b here

Answer:

Related questions

0 votes
0 votes
5 answers
1
go_editor asked Mar 24, 2020
3,452 views
The minimum number of scalar multiplication required, for parenthesization of a matrix-chain product whose sequence of dimensions for four matrices is $< 5,10,3,12,5 $ is...
0 votes
0 votes
4 answers
2
go_editor asked Mar 24, 2020
2,097 views
Dijkstra’s algorithm is based onDivide and conquer paradigmDynamic programmingGreedy approachBacktracking paradigm
0 votes
0 votes
6 answers
3
go_editor asked Mar 24, 2020
1,503 views
Match the following with respect to algorithm paradigms :$\begin{array}{clcl} & \textbf{List-I} & {} & \textbf{List-II} \\ \text{a.} & \text{Merge sort} & \text{i.} & \te...
0 votes
0 votes
4 answers
4
go_editor asked Jan 31, 2017
2,289 views
Red-black trees are one of many search tree schemes that are “balanced” in order to guarantee that basic dynamic-set operations take _____ time in the worst case.$O(1...