0
$\begingroup$

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order.

Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using quicksort.

I think $c_1 = c_2$ and $c_1=O(n^2)$? Is this correct ?

I am using the last element as a pivot for each partition.

$\endgroup$
  • 2
    $\begingroup$ The complexity of Quicksort depends on the pivot element that you've chosen. $\endgroup$ – Gokul Feb 17 at 10:32
  • $\begingroup$ lets say I am choosing last element as a pivot $\endgroup$ – Manoharsinh Rana Feb 17 at 10:34
  • $\begingroup$ That's a known bad strategy. Don't do that. Now think about how you would sort faster if a reasonable percentage of arrays that you sort are already sorted. $\endgroup$ – gnasher729 Feb 17 at 11:10
  • $\begingroup$ The question isn't answerable from the information given in your post. The answer depends on how you choose the pivot element. Just saying "quicksort" doesn't fully specify the algorithm you're using. Please edit the question to specify exactly what algorithm you're using. Don't just leave information in the comments; edit the question to make sure that everything that people need to answer is found in the question. $\endgroup$ – D.W. Mar 7 at 19:44
0
$\begingroup$

Quicksort is just an idea. There are algorithms and implementations.

Only stupid implementations will run in O(n^2) for sorted or reversed sorted arrays. Good sorting implementations actually check for elements in ascending or descending order at the beginning and end of the array and will handle either case in O(n), because wanting an array sorted without checking that it is sorted before is such a common case. Such implementations will fall back on Quicksort for handling the more difficult parts.

(It’s not just sorted arrays. You can have a general algorithm that sorts the concatenation of two sorted arrays in O(n), or a sorted array with fewer than O(n / log n) random elements added, or a sorted element with one random element changed).

$\endgroup$
-1
$\begingroup$

No, C1 =/= C2. Time complexity of quick sort depends on selection(position) of pivot element.Best case,Avg. case and worst case of various sorting technique are as: enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.