The Gateway to Computer Science Excellence
+24 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)$

in Algorithms by Veteran (52.2k points)
edited by | 2.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

+29 votes
Best answer

Applying Masters theorem,

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

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

Hence, answer is (C).

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
arujun sir it means theta determine big oh and omega.


theta equal to big oh and omega. ???

Is the comment made by @cse23 correct?
+1 vote

watch first 20 min, you will understand all about notations

by Junior (581 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.

by (177 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
50,737 questions
57,388 answers
105,414 users