in Algorithms
2,855 views
1 vote

solve the recurrence T(n)=2T(n/2)+n/lgn

in Algorithms
by
2.9k views

2 Comments

http://stackoverflow.com/questions/28093121/difference-between-solving-tn-2tn-2-n-log-n-and-tn-4tn-2-n-log-n

says can't apply master method,but I can apply master method and getting answer as Θ(nlglgn)

0

@Jon_Snow can you please help me to solve this

0

Subscribe to GO Classes for GATE CSE 2022

4 Answers

5 votes
 
Best answer
selected by

4 Comments

Thank you for your answer.I also solve this question using this equation.Got this question from Cormen but some where I saw we can't solve this question using Master theorem (now I  can't remember the source.)so I google it.Stack overflow also saying can't solve it.(you can find the link above.I can't understand the explanation).By applying this equation I got wrong answer here https://gateoverflow.in//3354/gate2008-it_44.
0
Comparing https://gateoverflow.in//3354/gate2008-it_44 and aT(n/b) + sqrt n..
a = sqrt 2 , b = 2, f(n) = root (n)
n^ (loga base b) = n^1/2 = root n
T(n) = O( sqrt(n)*logn)
According to asymptotic notation options A,B,C are correct..

But they asked exact solution (no option is in asymptotic notation) so checking initial value may eliminate some options.
T(1) = 1 and only option A satisfy this .

Here Masters theorem not gives wrong result, but from given option we have to refine exact solution because no option is in asymptotic form..
2
Thank you laser :) I think option 4 is not even asymptotically correct.
0
I will not be online for 1 week.If there is any mistake please comment.I will check it after 1 week
0
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
by

3 Comments

More conceptual method.. smiley

Harmonic Series Summation causes little trouble.

Should I byheart selected answer master's theorem to get nice rank.

Becz, there come certain concepts that become really tough to grasp like

in TOC - Decidability table u gave..sad  

1
not a necessity to by heart that. I'll not do that. I'll solve by this method only- and as you told Harmonic series is the only issue, but it is easier to by heart that :)

And for decidability also, I don't recommend studying that table- always know the reason and derive the answer- table I gave just for quick verification. Mostly GATE questions come from basic areas..
1
sir we can do it directly by extended masters theorem right?
0
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
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) +....

Related questions