2.7k views

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

1. $\Theta(n)$
2. $\Theta(n\log n)$
3. $\Theta(n^2)$
4. $\Theta(\log n)$
edited | 2.7k views
+1

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

0
Yes we can compute by that approach but this is a recurrence relation that means to compute T(1000) we need to know T(500)...for T(500) we need to know T(250)....for large n,  a large no of values have to be computed...

?

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

edited
+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 nlogba, it must be polynomially smaller. That is,f(n) must be asymptotically smaller than nlogba a by a factor of nͼ for some constant ͼ > 0".

In our case f(n) = lg n and nlogb= 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
I had given for $\epsilon = 0.5$ rt?
0

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

0
For that we already have a polynomial factor between $n$ and $n^{0.5}$
+4

clrs page 57:

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
+1

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

It's 2x1 + 22x2 + 23x3 + ... + 2k-1x(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) = 2T(n/2k) + lg n (n - 1) - [ n (lg n - 2) + 2]

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

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 .

edited by
+1 vote
 T(n) = 2T(n/2) + log n
T(1) = 1
Substitute n = 2^k

T(2^k)  = k + 2T(2^(k-1))
T(2^k)  = k + 2(k-1) + 4T(2^(k-2))
= k + 2(k-1) + 4(K-2) + 8T(2^(k-3))
= k + 2(k-1) + 4(K-2) + 8(k-3) + 16T(2^(k-4))
= k + 2(k-1) + 4(K-2) + 8(k-3) + ...... + 2^kT(2^(k-k))
= k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^kT(1)
= k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^k  --------(1)

2T(2^k) =     2k     + 4(k-1) + 8(K-2) + ...... + 2*2^k + 2^(k+1) --------(2)

Subtracting 1 from 2, we get below
T(2^k) = - k + 2 + 4 ......    2^(k-2) + 2^(k-1) + 2^k + 2^(k+1)
= - k + 2 * (1 + 2 + 4 + ..... 2^k)
= -k + [2*(2^k - 1)] / [2-1]
= -k + [2*(2^k - 1)]

T(n) = -Logn + 2*(n - 1)

T(n)  = Θ(n) 

1
2