The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

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

asked in Algorithms by Veteran (59.5k points)
edited by | 1.5k views

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

3 Answers

+25 votes
Best answer

Applying Masters theorem,

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

So, it cannot be  $\Omega(n^2)$.

Hence, answer is $(C)$.

answered by Active (3.5k points)
edited by
Why not D)?

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

$\Theta \implies O \wedge \Omega$. So, D is true.
C) will true for $\Omega (n) and \Omega (n log n)$ in both cases, rt?
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
yes srestha lower bound will be true for both Ω(n)andΩ(nlogn).
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 ??
@for better understanding of master theorem see proofof  master theorem in cormen....
@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.
got now thanks sir
+1 vote

watch first 20 min, you will understand all about notations

answered by Junior (605 points)
0 votes

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

P.S. Not mine.

answered by (175 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,111 questions
45,619 answers
49,291 users