in Algorithms edited by
5,206 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)$
in Algorithms edited by
5.2k views

41 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
0

@Jon_Snow can you please help me to solve this

0
0

option C is more than sufficient I think.

The function n/logn is less than nlog ba but not polynomially. But it surely less than option C asymptotically

0
0
How are you predicting like that directly??? And masters theorem is not applicable so I solved by backward substituion.

I am stuck at 1+1/2+1/3+1/4+......+1/k

What is this series equal to???
0
0

@Rahul. COnsider the master theorem rule :

if f(n) = O( nlog ba ) then T(n) = $\Theta$(nlog ba logn)

Now, lets assume that f(n) was 'n'(Here its indeed less than n). So, B would suffice. But not sure of option C.

0
0
Ohk. But nothing can be said surely, i am getting n(1+1/2+1/3+......+1/k). So I think this series is equal to logn. So 2 will be answer???
0
0

but can we apply MT here? As the difference between nlog band n/log n is logarithmic and not polynomial?

0
0
No, we cant apply master theorem.

@Rahul. Your series is converging. Also see the log graph and intuitive graph for the series. I will be same.

 

SO, B will be the option.  But why not C? We want tightest bound.
0
0
Sushant 1+1/2+...1/k will be greater than k but not much greater we can overcome this by some constant. and k= logn so 2) is the answer.
0
0
:) We want tightest bound. Thats what i am wondering that if C will suffice.
0
0
Yup I did a really silly mistake.
0
0

if n0.99999... > n/logn   for large 'n' then we definitely bound by option C. I think this will hold if we check the graph for logn.

0
0
how can 1 + 1/2 + 1/3 ......1/k   be greater than k?   As K increases, increments will be very small.
0
0
Sorry, really bad mistake.☺
1
1
i am stuck here-

n/logn + n/log(n/2)  + n/log(n/4) + .....

how to solve this??
0
0

You need to take n=2k and then try

0
0
i am not able to calculatye it..can someone give the soltuion?
0
0

T(2k) = 2T(2k-1) + 2k/k

So, S(k) = 2S(k-1) + 2k/k

Thus, the sequence would be 2k/K + 2.2k-1/(k-1) .......

= 2k[1/k + 1/(k-1) + 1/(k-2) ..........]

0
0

here you are taking n= 2k

then it becomes T(2k) = 2T(2k-1) + 2k/k

then you are substituing m = 2k .

and equation becomes s(m) =2S(m-1) + ..

what happens to 2k/k term?how to replace it wiht m??

0
0

We just took S(k) = T(2k

0
0
edited by
0
0
This example is different
0
0
@sushant you were correct. Answer is 3.

1+1/2+....1/k =log k

And log k = log log n.
0
0
@sushant,this can be solved by master's theorem...there is a rule for that.

i am not getting answer through your method.stuck in the calculation
0
0
@Akriti. Let me know if you get that rule.
0
0
@Akriti. I didnt know that negative powers of logn are also allowed to apply the auxillary rule of Masters theorem.

Amazing video !! Thanks a lot. :)
0
0
Actually you cannot solve it by masters theorem. You can find it on wikipedia maters theorem and section inadmessible forms. But I think maybe the formula provdied by Ravindra Sir can used for negative powers and we can solve problem like this very easily.

@Akriti thanks for video. Learned new formula.
0
0
its not a new formula @rahul..its extended master's theorem..it covers everything what master theorem was unable to
2
2
@sudsho ,Thanks. But if in exam it is asked can it be solved by masters??? Then it should be yes or no??
0
0
they will nt ask whether u can solve it or not...they will just say u to solve it...then u can solve any question using this...
1
1
Okay☺
1
1
welcome :)
0
0

Well i hope now you got it

0
0
thanks for the details. but my approach was different. answer added
0
0

Aswer is O(n lgn)

Check the last paragraph of this...

0
0
@Nirmal Gaur, Please can you kindly solve. It'll be way better. Literally. :) (y)
0
0

Here you can't apply master theorem ...

so either solve it using substitution method or recursive tree method...

get it here..

https://stackoverflow.com/questions/12119799/solve-the-recurrence-tn-2tn-2n-logn

0
0
@Rupendra What is the problem with applying master theorem?
0
0
O(nloglogn) is the correct answer
1
1

11 Answers

3 votes
3 votes
Best answer

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

2 Comments

master's theorem : 2)-b case answer is  O (nlog22 log log n) = O(n log log n)

1
1

This is wrong explanation:

master theorm can't be applied here...

see: https://en.wikipedia.org/wiki/Master_theorem#Inadmissible_equations

0
0
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
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
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
1
sir we can do it directly by extended masters theorem right?
0
0
5 votes
5 votes

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
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
2
Thank you laser :) I think option 4 is not even asymptotically correct.
0
0
I will not be online for 1 week.If there is any mistake please comment.I will check it after 1 week
0
0
1 vote
1 vote

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

1 comment

yes answer is c well my aprroach is much easier .

i forgot to return the value which i let just
0
0
Answer:

Related questions