Determining growth function and Big O

Question

Before anyone asks, yes this was a previous test question I got wrong and knew I got wrong because I honestly just don't understand growth functions and Big O. I've read the technical definition, I know what they are but not how to calculate them. My textbook gives examples off of real-life situations, but I still find it hard to interpret code. If someone can tell me their thought process on how they determine these, that would seriously help. (i.e. this section of code tells me to multiply n by x, etc, etc).

public static int sort(int lowI, int highI, int nums[]) {

        int i = lowI;
        int j = highI;

        int pivot = nums[lowI +(highI-lowI)/2];

        int counter = 0;

        while (i <= j) {
            while (nums[i] < pivot) {
                i++;
                counter++;
            }
            while (nums[j] > pivot) {
                j--;
                counter++;
            }

            count++;
            if (i <= j) {
                NumSwap(i, j, nums); //saves i to temp and makes i = j, j = temp
                i++;
                j--;
            }
        }

        if(lowI< j)
        {    
            return counter + sort(lowI, j, nums);
        }    
        if(i < highI)
        {    
            return counter + sort(i, highI, nums);
        }

        return counter;

    }

Answer 1

It might help for you to read some explanations of Big-O. I think of Big-O as the number of "basic operations" computed as the "input size" increases. For sorting algorithms, "basic operations" usually means comparisons (or counter increments, in your case), and the "input size" is the size of the list to sort.

When I analyze for runtime, I'll start by mentally dividing the code into sections. I ignore one-off lines (like int i = lowI;) because they're only run once, and Big-O doesn't care about constants (though, note in your case that int i = lowI; runs once with each recursion, so it's not only run once overall).

For example, I'd mentally divide your code into three overall parts to analyze: there's the main while loop while (i <= j), the two while loops inside of it, and the two recursive calls at the end. How many iterations will those loops run for, depending on the values of i and j? How many times will the function recurse, depending on the size of the list?

If I'm having trouble thinking about all these different parts at once, I'll isolate them. For example, how long will one of the inner for loops run for, depending on the values of i and j? Then, how long does the outer while loop run for?

Once I've thought about the runtime of each part, I'll bring them back together. At this stage, it's important to think about the relationships between the different parts. "Nested" relationships (i.e. the nested block loops a bunch of times each time the outer thing loops once) usually mean that the run times are multiplied. For example, since the inner while loops are nested within the outer while loop, the total number of iterations is (inner run time + other inner) * outer. It also seems like the total run time would look something like this - ((inner + other inner) * outer) * recursions - too.