1
$\begingroup$

Say I have a dynamic array of the proper length $n$. A sort pivot is given.

I run the sort algorithm, wait, and get $j$ unbalanced pivots. Is the time complexity $O(n\log n)$ or has it destabilized to quadratic in the best case? I believe that it will be useful to use recurrences to model each scenario, but not sure how to set up from there.

$\endgroup$
  • $\begingroup$ Please don't delete your post (or delete the content of your post) after someone has taken the time to provide you with an answer. That is not considered acceptable here. This site exists not only to help you, but to help others who might have a similar question in the future. When people answer, they might be answering based on the assumption that it will help others as well, so it's not fair to them to delete your question after getting an answer. $\endgroup$ – D.W. Oct 12 '18 at 2:26
  • $\begingroup$ I am unclear on the question. Do you mean $j$ pivots total or per recursive part after $k$ levels of recursion? $\endgroup$ – HackerBoss Oct 12 '18 at 3:12
  • $\begingroup$ OK. Can you provide a link to the question that this is a duplicate of? The way we handle duplicates is by closing as a duplicate, rather than by deleting the question. You can nominate your question to be closed as a duplicate by clicking "flag" under the question, selecting "should be closed..." then "duplicate of..." and identifying the question that this is a duplicate of. $\endgroup$ – D.W. Oct 12 '18 at 3:12
  • $\begingroup$ No worries. You're not going to get suspended for a single case of misunderstanding how to handle a duplicate. My goal is to communicate how we prefer to see the situations handled. Your flag has successfully caused the question to be closed as a duplicate. $\endgroup$ – D.W. Oct 12 '18 at 4:22
3
$\begingroup$

This answer is for the following version of the post:

Say I have an array sized $n$. A quicksort pivot is balanced when each side of the partition ends up with $n/c$ ($c$ is a fixed constant). Else, the partition in unbalanced.

In both these cases, partitioning takes $pn$ time ($p=O(1)$). Let's say I run quicksort and after one balanced pivot, I get $j$ unbalanced pivots. Is the runtime still $O(n\log n)$? I believe that it will be useful to use recurrences, but not sure how to set up from there.

The running time should still be $O(n\log n)$. Intuitively, the size of the array decreases by a factor of $c$ every $j+1$ recursion levels, so the total number of levels would be $(j+1)\log_c n = O(\log n)$. The work at every level is $O(n)$, for a total of $O(n\log n)$.

How would a recurrence look? We will have $j+1$ different functions: $T_j$ for the balanced levels, and $T_0,\ldots,T_{j-1}$ for the unbalanced levels. The recurrences are $$ T_j(n) = \max_{n/c \leq m \leq n-n/c} T_0(m) + T_0(n-1-m) + pn, \\ T_i(n) = \max_{1 \leq m < n/c} T_{i+1}(m) + T_{i+1}(n-1-m) + pn. $$ Actually solving the recurrences could be a chore, so it's better to formalize the intuitive argument outlined above.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

It is because we can use two recurrences, one for balanced and one for unbalanced, and see that summing them yields $O(nlogn)$.

| cite | improve this answer | |
$\endgroup$

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