3,528 views

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)$

@Rupendra What is the problem with applying master theorem?

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)

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

This is wrong explanation:

master theorm can't be applied here...

$$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.

by

More conceptual method..

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..

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

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

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

1
1,798 views