Someone plz explain it...It is given in **Coreman book of Algorithms that Master theorem cannot be applied to T(n)=2T(n/2)+nlgn because g(n)=n and f(n)=nlgn are not polynomially comparable....**.

So can we apply master theorem in above question....?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

Which one of the following correctly determines the solution of the recurrence relation with $T(1) = 1$?

$$T(n)= 2T\left(\frac {n} {2}\right) + \log n$$

- $\Theta(n)$
- $\Theta(n\log n)$
- $\Theta(n^2)$
- $\Theta(\log n)$

+28 votes

Best answer

$f(n) = \log n$

$a = 2, b = 2 \implies n^{\log_b a} = n$

So, $f(n) = \log n = O\left(n^{1-\epsilon} \right)$, we can take any $\epsilon$ from $0$-$1$ for example $0.5$ which gives $\log n = O(\sqrt(n))$, whose proof is given here: http://math.stackexchange.com/questions/145739/prove-that-logn-o-sqrtn

So, Master theorem Case 1, and answer will be $O\left(n^{\log_2 2}\right) = O(n)$

Alternate way:

$T(1) = 1 \\ T(2) = 2T(1) + \log 2 = 3 = 3n - 2\\T(4) = 2T(2) + \log 4 = 8 = 3n - 4 \\T(8) = 2T(4) + \log 8 = 19 = 3n - 5\\ T(16) = 2T(8) + \log 16 = 42 = 3n - 6$

The second term being subtracted is growing at a lower rate than the first term. So, we can say $T(n) = O(n)$.

+2

@Arjun Sir: I have some some confusion if we can apply master theorem here. From CLRS: "In the first case, not only must f(n) be smaller than n^{logba}, it must be polynomially smaller. That is,f(n) must be asymptotically smaller than n^{logba} a by a factor of n^{ͼ} for some constant ͼ > 0".

In our case f(n) = lg n and n^{logba }= n. So (lg n)/n < n^{ͼ} holds for some ͼ > 0 ?

I tried plotting graphs for ͼ=0.5 and it seems that the inequality holds, but how to prove it without graph?

0

That proves that log n is asymptotically smaller than n^{1/2}, but says nothing about it being polynomially smaller.

0

$T(\frac{n}{2}) = 2T(\frac{n}{4})+log(\frac{n}{2})$

$=2T(\frac{n}{4})+log(n)-1$

$T(\frac{n}{4}) = 2T(\frac{n}{8})+log(\frac{n}{4})$

$ =2T(\frac{n}{8})+log(n)-2$

$T(\frac{n}{8}) =2T(\frac{n}{16})+log(n)-3$

-----------------------------------------------------------------

$T(n) = 16T(\frac{n}{16})+15log(n) -34 $

.

.

$T(n) = 2^{k} T(\frac{n}{2^{k}})+(2^{k}-1)log(n) + const -----(1)$

Given , $\frac{n}{2^{k}} =1$

$log n = k$

Equation 1 become

$n+(n-1)logn - c $

Therefore it is of $O(n log(n))$

What is wrong with my approach

$=2T(\frac{n}{4})+log(n)-1$

$T(\frac{n}{4}) = 2T(\frac{n}{8})+log(\frac{n}{4})$

$ =2T(\frac{n}{8})+log(n)-2$

$T(\frac{n}{8}) =2T(\frac{n}{16})+log(n)-3$

-----------------------------------------------------------------

$T(n) = 16T(\frac{n}{16})+15log(n) -34 $

.

.

$T(n) = 2^{k} T(\frac{n}{2^{k}})+(2^{k}-1)log(n) + const -----(1)$

Given , $\frac{n}{2^{k}} =1$

$log n = k$

Equation 1 become

$n+(n-1)logn - c $

Therefore it is of $O(n log(n))$

What is wrong with my approach

+1

@Gokou: The last term which you are taking as a constant in equation (1) is not actually a constant.

It's 2x1 + 2^{2}x2 + 2^{3}x3 + ... + 2^{k-1}x(k-1)

So if you solve this series, you should get the correct answer. I remember solving this way a little while ago, see if you can solve it and post the solution, please.

Edit: I think this way of solving recurrence is not correct because we're assuming the input size to be a power of 2. We must also prove that the recurrence holds for other input sizes.

Edit2: The sum of this series would be n(lg n - 2) + 2.

Reference:

So T(n) = 2^{k }T(n/2^{k}) + lg n (n - 1) - [ n (lg n - 2) + 2]

Solving it you'll get T(n) = cn - lg n - 2

+13 votes

**Using Extended Master Theorem**

$a=2 , b=2 , k=0 ,p= 1$ Case $1$ Follows .

Hence the Given function is $\Theta (n^{\log_2 2}) \Rightarrow \Theta (n)$

Reference : Extended Master Theorem

**Using back substitution . **

+1 vote

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,558 answers

146,289 comments

62,306 users