edited by
16,475 views
35 votes
35 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$$

  1. $\Theta(n)$
  2. $\Theta(n\log n)$
  3. $\Theta(n^2)$
  4. $\Theta(\log n)$
edited by

3 Answers

Best answer
45 votes
45 votes

$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))$, proof of which 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)$.

Correct Answer: $A$

edited by
32 votes
32 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 .

edited by
3 votes
3 votes
 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) 
Answer:

Related questions

47 votes
47 votes
3 answers
1
go_editor asked Sep 28, 2014
13,512 views
The number of distinct minimum spanning trees for the weighted graph below is _____
44 votes
44 votes
7 answers
3