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

1 votes
1 votes

HERE mastre theorem is not applicable . 

we can use this formula . it is helpfull for all cases.

1 flag:
✌ Prohibited (Hira Thakur “Copyright issue possible (screemshot is taken without mentaion it's source)”)
0 votes
0 votes

T(n)=2T(n/2)+n/log n comparing with T(n)=aT(n/b)+f(n) where b>1 f(n) is positive

applying master mathed-

nlog2=n > f(n) so probably case1 applicable ....hence the solution is ⊖(n)


but some times the gap between f(n) and nlogb a is small and it is log n in that that case the solution shifted with one log  value. but here log ≍ √n hence f(n) is approximate n/√n=√n hence final solution is ⊖(n)

0 votes
0 votes
O(n)

solved it by back subsitution and made  some assumption ...with some progression....like      1/ logn +1/ log(n/2) + 1/log(n/4) +....
Answer:

Related questions

0 votes
0 votes
5 answers
5
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
6
go_editor asked Mar 24, 2020
2,096 views
Dijkstra’s algorithm is based onDivide and conquer paradigmDynamic programmingGreedy approachBacktracking paradigm
0 votes
0 votes
6 answers
7
go_editor asked Mar 24, 2020
1,502 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
8
go_editor asked Jan 31, 2017
2,285 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...