Here is the SelectionSort program I wrote. Is my complexity analysis correct?
public static void selectionSort(int[] numbers) {
for (int i = numbers.length - 1; i >=1; i--)
{
int maxPos = 0;
for (int j = 1; j < i; j++)
{
if (numbers[j] > numbers[maxPos])
{
maxPos = j;
}
}
if (numbers[maxPos] > numbers[i])
{
int temp = numbers[i];
numbers[i] = numbers[maxPos];
numbers[maxPos] = temp;
}
}
}
Difficulty analysis
Outter Loop (comparison and purpose): 2 ops completed n times = 2n ops
Purpose maxPos: n ops
Inner loop (comparison and purpose): 2 operations performed 2n ^ 2 times = 2n & sup2; OPS
Comparison of array elements (references to two arrays and comparison): 3n & sup2; OPS
Purpose of the new maxPos: n & sup2; OPS
Comparison of array elements (references to two arrays and comparison): 3n & sup2; OPS
Purpose and array reference: 2n & sup2; OPS
Purpose and 2 array references: 3n & sup2; OPS
Purpose and array reference: 2n & sup2; OPS
The total number of primitive operations
2n + n + 2n? + 3n? + n ^ 2 + 3n & sup2; + 2n? + 3n? + 2n? = 16n? + 3n
Reduction to Big Oh (n & sup2;)
? , ...