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

The code is as follows:

int maxPos (int[]A, int a, int b){  int max, maxPos; max = A[a]; maxPos = a; for (int i=a+1; i<=b; i++)  if ( A[i] > max ){   max = A[i];  maxPos = i; }  return maxPos; } void exchange (int []A, int a, int b){ int temp; temp = A[a];  A[a] = A[b];  A[b] = temp; }  void maxSort (int []A){  for (int i=A.length-1;i>0;i--)exchange (A, i, maxPos (A, 0, i)); } 

I believe the worst case is W(N) = n(n-1)/2

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

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

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

The code is as follows:

int maxPos (int[]A, int a, int b){ int max, maxPos; max = A[a]; maxPos = a; for (int i=a+1; i<=b; i++) if ( A[i] > max ){ max = A[i]; maxPos = i; } return maxPos; } void exchange (int []A, int a, int b){ int temp; temp = A[a]; A[a] = A[b]; A[b] = temp; } void maxSort (int []A){ for (int i=A.length-1;i>0;i--)exchange (A, i, maxPos (A, 0, i)); } 

I believe the worst case is W(N) = n(n-1)/2

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

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

The code is as follows:

int maxPos (int[]A, int a, int b){ int max, maxPos; max = A[a]; maxPos = a; for (int i=a+1; i<=b; i++) if ( A[i] > max ){ max = A[i]; maxPos = i; } return maxPos; } void exchange (int []A, int a, int b){ int temp; temp = A[a]; A[a] = A[b]; A[b] = temp; } void maxSort (int []A){ for (int i=A.length-1;i>0;i--)exchange (A, i, maxPos (A, 0, i)); } 

I believe the worst case is W(N) = n(n-1)/2

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