1.4k views

Suppose $T(n) =2T (\frac{n}{2}) + n$, $T(0) = T(1) =1$

Which one of the following is FALSE?

1. $T(n)=O(n^2)$

2. $T(n)=\Theta(n \log n)$

3. $T(n)=\Omega(n^2)$

4. $T(n)=O(n \log n)$

edited | 1.4k views
+3

It is the recurrence relation of $Merge-Sort$. The time complexity of merge sort is $Θ(nlogn)$.
The option (C) is false!

Applying Masters theorem $T(n) = \Theta (n \log n)$ So, it can't be  $\Omega(n^2)$

edited by
–1
Why not D)?
+2

here we are asked to choose false option, so option D is not false here. You can think of merge sort algorithm which has same type of algo and its time complexity is O(nlog n).

+8
$\Theta \implies O \wedge \Omega$. So, D is true.
0
C) will true for $\Omega (n) and \Omega (n log n)$ in both cases, rt?
+6
theta(nlogn) means our value can be >= as well <= of nlogn

T(n) is upper as well lower bounded by nlogn.

(A) is O(n2) so value of T(n) is less than n2 which satisfy lower bounded by nlogn

(C) is omega(n2) means T(n)>= n2 which is not possible because it is upper bounded by nlogn

(D) tells that it is less than <=nlogn  which is fine
0
yes srestha lower bound will be true for both Ω(n)andΩ(nlogn).
+1
i have doubt here when we solve the value of T(n) using master theorem  we have used ⊝( nlogn) why we use theta here?? why not any other notation ??
+1
@for better understanding of master theorem see proofof  master theorem in cormen....
+3
@Kunal $\Theta$ implies $O$ and $\Omega$. And Master theorem is for $\Theta$. We can instead use $O$ or $\Omega$ also as both are implied by $\Theta$ but in any case the meaning of these must be known correctly before using.
+1
got now thanks sir
+1 vote

watch first 20 min, you will understand all about notations

If you are not getting how Master theorem works step by step, you can refer this blog post:

https://devsathish.wordpress.com/2012/01/19/master-theorem-with-examples/

P.S. Not mine.

1
2