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

**The option (C) is false!**

The Gateway to Computer Science Excellence

+29 votes

Best answer

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

+9

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

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

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

0 votes

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,388 answers

198,576 comments

105,414 users