My prof has a sense of humour. We're supposed to analyse the following method for complexity; it's a method to sort an array of ints, written in java.

public static void slowSort(int theArray[]) {\r\n  // For each value of i, find the largest value in theArray[0..i]\r\n  // and move it into the last position -- kind of like selection sort,\r\n  // but the details are different.\r\n  for (int i = theArray.length-1; i > 0; i--) {\r\n    int maxIndex = 0; // the index of the largest value in theArray[0..i]\r\n    for (int j = 0; j <= i; j++) {\r\n      // Check to see if theArray[j] is the largest value in theArray[0..i]\r\n      // Do this by comparing it will all other values in this range\r\n      boolean isMax = true;\r\n      for (int k = 0; k <= i; k++) {\r\n        if (theArray[k] > theArray[j])\r\n          isMax = false;\r\n      } // end for\r\n      if (isMax)\r\n        maxIndex = j;\r\n    } // end for\r\n    // move theArray[maxIndex] into position theArray[i] by moving\r\n    // elements down\r\n    int maxElement = theArray[maxIndex];\r\n    for (int j = maxIndex; j < i; j++)\r\n      theArray[j] = theArray[j+1];\r\n    theArray[i] = maxElement;\r\n  } // end for\r\n} // end slowSort

Now, I haven't done any math in around ten years, so I'm running at a bit of a disadvantage here. However, it seems to me that the nastiest part of the code is the k loop; it gets executed a LOT, though the methodology for slopping the array elements around at the very end of the i loop is also a complete dog.

It looks to me that the dominant factor affecting complexity is the k loop. My quick feel for it is that this makes the complexity O(n*n), hand waving the various other bits and pieces. Anybody can tell me if I'm way off...?