Deriving Time Complexity from an algorithm

Question

I am trying to learn about time complexity of an algorithm. My professor has pushed it beyond Big O and wants us to be able to derive an algorithm to a mathematical function. I am having a hard time conceptualizing how this is done and was looking for help. In my class notes, a selection sort algorithm was provided (as shown in the code below). The notes asked the following question: "Derive a function f(n) that corresponds to the total number of times that minIndex or any position of nums is modified in the worst case. Now the notes tell me the answer is f(n)= 1/2n^2 + 5/2n + 3. I was wondering if anyone could explain how this occurs.

My professor told us to count the operations in the inner loop and work our way out. so I believe that at worst case in the inner loop the if statement always executes, this would mean we run the loop n-i-1 times, I get these values by taking n (the boundary that the for loop has to be less than and subtracting it by the starting condition (i+1). Then I look at the outer loop and I see it goes from i until it reaches n-1, so it could be written as (n-1)-i or just like the inner loop, n-i-1. Looking further there are three modifications in the outer loop so we get (n-i-1)+3 ( could I write it as (n-i+2)?

The number of modification at the worst case for the inner loop: n-i-1

The number of modifications at the worst case for the outer loop: (n-i-1)+3

now I would like to know how do you go from counting the two different modifications done and becoming f(n)= 1/2n^2 + 5/2n + 3.

public static void selectionSort(int[] nums) {

        int n = nums.length;
        int minIndex;

        for(int i = 0; i < n-1; i++) {
            //find the index of themin number.
            minIndex = i;

            for(int j = i+1; j < n; j++) {
                if(nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
                int temp = nums[i];
                nums[i] = nums[minIndex];
                nums[minIndex] = temp;
            }
        }
}

Answer 1

How many times does outer loop run?
n - 1 times.

How many times does inner loop run, for each iteration of outer loop?
From n - 1 times down to 1 time, as outer loop progresses, so on average:
((n - 1) + 1) / 2 = n / 2 times.

So, how many times does inner loop run in total?
(n - 1) * (n / 2) = n^2 / 2 - n / 2 times.

How many times is minIndex modified?
Once per outer loop + once per inner loop:
(n - 1) + (n^2 / 2 - n / 2) = n^2 / 2 + n / 2 - 1 times.

How many times is a position of nums modified?
Twice per inner loop:
2 * (n^2 / 2 - n / 2) = n^2 - n times.

What is total number of modifications?
(n^2 / 2 + n / 2 - 1) + (n^2 - n) = (3*n^2 - n) / 2 - 1 times.
Or 1½n² - ½n - 1

---

That's not the same answer as you said your notes has, so let's prove it.

First, we add debug printing, i.e. print any modification including a modification number.

public static void selectionSort(int[] nums) {
                                              int mod = 0;
    int n = nums.length;
    int minIndex;

    for(int i = 0; i < n-1; i++) {
        //find the index of themin number.
        minIndex = i;                         System.out.printf("%2d: minIndex = %d%n", ++mod, i);

        for(int j = i+1; j < n; j++) {
            if(nums[j] < nums[minIndex]) {
                minIndex = j;                 System.out.printf("%2d: minIndex = %d%n", ++mod, j);
            }
            int temp = nums[i];
            nums[i] = nums[minIndex];         System.out.printf("%2d: nums[%d] = %d%n", ++mod, i, nums[minIndex]);
            nums[minIndex] = temp;            System.out.printf("%2d: nums[%d] = %d%n", ++mod, minIndex, temp);
        }
    }
}

Worst case is sorting an array of descending numbers, so lets try 3 numbers:

int[] nums = { 3, 2, 1 };
selectionSort(nums);
System.out.println(Arrays.toString(nums));

We'd expect (3*n^2 - n) / 2 - 1 = (3*3^2 - 3) / 2 - 1 = 24 / 2 - 1 = 11 modifications.

 1: minIndex = 0
 2: minIndex = 1
 3: nums[0] = 2
 4: nums[1] = 3
 5: minIndex = 2
 6: nums[0] = 1
 7: nums[2] = 2
 8: minIndex = 1
 9: minIndex = 2
10: nums[1] = 2
11: nums[2] = 3
[1, 2, 3]

Yup, 11 modifications.

Lets try 9:

int[] nums = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };

(3*n^2 - n) / 2 - 1 = (3*9^2 - 9) / 2 - 1 = 234 / 2 - 1 = 116 modifications.

  1: minIndex = 0
  2: minIndex = 1
  3: nums[0] = 8
  4: nums[1] = 9
  5: minIndex = 2
  6: nums[0] = 7
      . . .
111: nums[6] = 7
112: nums[8] = 8
113: minIndex = 7
114: minIndex = 8
115: nums[7] = 8
116: nums[8] = 9
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Yup, 116 modification.

Formula verified by empiric evidence:
f(n) = (3*n^2 - n) / 2 - 1