edited by
1,368 views
2 votes
2 votes

When the recurrence relation for both are same , why they both getting different result?

Q1. In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?

ANSWER: recurrence relation gives,T(N) = T(N/3) + T(2N/3) + N on solving T(N) = N(log3/2N)

Q2. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort? 

ANSWER:recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving we get \theta(n Log n).

My doubt  is If for first case it is N(log3/2N) then for  second case also it should be N(log4/3N) BUT its not. WHY?

edited by

3 Answers

0 votes
0 votes
Yes, the answer will be O (logbase4/3 n).

Create the recursive tree for the given recurrence relation then you'll find that the T (3n/4) will give you greater depth so the stopping condition will be like (3/4)^k = 1. Hence k=4/3. So answer will be O (logn) with base of 4/3.

And I didn't get your first question properly. Please elaborate it Will ya !
0 votes
0 votes

answer will be  N(log4/3N)  in second case also but it is just rounded off because 4/3=1.333=2 you can write it as 4/3 or 2

similarly for first case you can round off 3/2 as 2 so that it will become as nlogn 

if you solve the recurrence relation without taking any approximation you will get the your desired answer

0 votes
0 votes
you can understand it like this. what i feel.

Merge sort is an outplace algorithm and we need an additional auxilliary space for the data to be tracked.

Quick sort is an in place algorithm and it works on the data values needed to be sorted. and so it needs O(logn) pointers for the data to be tracked more efficiently.

Moreover we know that more space complexity mean less time complexity it will have..

so quick sort will have theta(nlogn)

Related questions

0 votes
0 votes
2 answers
2
_Madhuri asked Oct 9, 2021
634 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
0 votes
0 votes
0 answers
3
1 votes
1 votes
2 answers
4
Ravi Dubey asked Aug 2, 2018
829 views
Could a binary search tree be built using o(n lg n) comparisons in the comparisonmodel? Explain why or why not.