Register

UGC NET CSE | January 2017 | Part 3 | Question: 31

• edited by
5,241 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
User Avatar

11 Answers

0 votes
0 votes

 

 

 $T(n)=Θ(n^{logb_a}loglogn)$

 $T(n)=Θ(nloglogn)$

here a=2,b=2,k=1,p=-1 apply second case $a=b^{k}$ where p=-1

 

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
5 answers
1
go_editor asked Mar 24, 2020
3,625 views
UGC NET CSE | January 2017 | Part 3 | Question: 34
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 $630$ $580$ $480$ $405$
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...
User Avatar
0 votes
0 votes
4 answers
2
go_editor asked Mar 24, 2020
2,252 views
UGC NET CSE | January 2017 | Part 3 | Question: 35
Dijkstra’s algorithm is based on Divide and conquer paradigm Dynamic programming Greedy approach Backtracking paradigm
Dijkstra’s algorithm is based onDivide and conquer paradigmDynamic programmingGreedy approachBacktracking paradigm
User Avatar
0 votes
0 votes
6 answers
3
go_editor asked Mar 24, 2020
1,588 views
UGC NET CSE | January 2017 | Part 3 | Question: 36
Match the following with respect to algorithm paradigms : ... $\text{a-ii, b-i, c-iii, d-iv}$ $\text{a-iii, b-ii, c-i, d-iv}$
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...
User Avatar
0 votes
0 votes
4 answers
4
go_editor asked Jan 31, 2017
2,378 views
UGC NET CSE | January 2017 | Part 3 | Question: 33
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)$ $O( \lg n)$ $O(n)$ $O(n \lg n)$
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...
User Avatar
Link Copied!