1
$\begingroup$

I'm having trouble approaching this average case analysis in terms of key comparisons.

The pseudo-code is as follows:

maxSort(Array) {
    for (int i = Array.length - 1; i > 0; i--) {
        x = i - 1
        max_i = findMaxPos(x) # performs x key comparisons
        swapValues(max_i, i)
    }
}

findMaxPos returns position of largest value between index 0 and x of the array. Performs x key comparisons.

I believe the worst case is W(N) = n(n-1)/2 where n is the size of the array.

I am unsure how to contextualize the algorithm in an average case in terms of key comparisons. Should I create a decision tree and show the lower bound for average behavior? Or is there a way to use permutations? Any help is greatly appreciated

Edit: For context, the original question is asking for the number of key comparisons in the worst and average case. While working out the worst case was relatively straight forward I'm unsure how to write some sort of proof or perform analysis to show the average is the same

$\endgroup$
9
  • $\begingroup$ Do you mean comparisons in maxPos function? $\endgroup$
    – zkutch
    Mar 14 at 21:51
  • $\begingroup$ @zkutch yeah, it's my interpretation that the if statement within the for loop in maxPos function is the key comparison $\endgroup$ Mar 14 at 21:52
  • $\begingroup$ Amount of comparisons in loop, in maxPos function, is fixed and depends on loops lower and upper bounds i.e. $a$ and $b$, so it is constant, when bounds are fixed. $\endgroup$
    – zkutch
    Mar 14 at 22:00
  • $\begingroup$ The amount of comparisons doesn't depend on the input. $\endgroup$ Mar 14 at 22:07
  • 1
    $\begingroup$ @Dmitry updated to psuedo code $\endgroup$ Mar 14 at 22:35
0
$\begingroup$

The number of comparisons on an array of length $n$ is $\binom{n}{2}$, regardless of the contents of the array. Therefore all of the following are $\binom{n}{2}$: the worst-case number of comparisons, the best-case number of comparisons, and the average-case number of comparisons, with respect to any input distribution.

$\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.