Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
Only the base of log will change according to the number of partitions created.
2 partitions - Base of log will be 2
3 partitions - Base of log will be 3
4 partitions - Base of log will be 4
So on
Correct. It should be noted, though, that all log bases are equivalent up to a constant factor. Also, the performance of quicksort cannot be improved by having more partitions because the constant factor C in front, as in CNlog(base whatever)N, will increase to more than offset anything gained by a larger base for the log.
In the quicksort algorithm,we select one pivot element and partition the array according to that one and then sort the two partitions.
What will be the changes in complexity if we select more than one pivot and partition the array in 3 or more partitions ??
please post the answer!!!and i m new to this (O) big o concept...i can only find the theory part .how to calculate thos big o!!!plz refer me some sites!!!thanks
Any of those variants of Quicksort are still NlogN. If you select k pivots, you will get something like (k-1) (base k+ 1) N operations for integer k >= 2. This expression is smallest for k=2 but still O(NlogN) for any constant K because log(base x)N is O(log(base y)N) for all x, y > 1. This is so because log(base x) N = [log (base y) N] / [log (base y) x], and that denominator is constant. So all log runtimes are separated by only a constant factor.
I don't have an answer, but this is what I think: If we partition with 2 pivots, then we make 3 parts and call partition again for each of those three.
function f(N)
if N <=1 return;
partition -> Order N
f(N/3); f(N/3); f(N/3);
I am not sure how to solve this recurrence. Is it NLog(base 3) N?
if we use 2 element as a pivot (suppose 1st and last element) then we partisan the array into three part and we use quick shot in every partisan
- Bidhan Pal June 02, 2012So the new recurrence relation became
T(n) = 3 x T(n/3) + O(n)
we assume the array partisan in equal parts and finding the exact position of pivot is O(n)
now applying master theorem f(n) = O(n); a=3; b=3;
f(n) = O(n ^ (log a/log b))
so complexity is O(nlogn)
Now if we take k-1 pivot element the partisan the array in k part so
T()= k x T(n/k) + O(n)
which complexity is also O(n long)
so irrespective of how many partisan we do the complexity of quick sort remains same.