Order and Growth Function of Loops

Question

I'm trying to find the order and growth function of this for loop inside a function which takes in an array of length n > 2.

This function orders the array in ascending order. I'm trying to find the order for a worst case scenario: when the array is ordered initially in descending order and the function therefore has to iterate through the array many times to sort it.

Here is the loop:

        for (int next = 1; next < array.length; next++) {
            int value = array[next];
            int index = next;
            while (index > 0 && value < array[index - 1]) {
                array[index] = array[index - 1];
                index--;
            }
            array[index] = value;
        }

I've been racking my brains trying to figure it out. Writing tests, writing tons of functions down and I get close, but never right on. How would you go through such a loop to find it's order and growth function?

Any direction would greatly be appreciated. Thank you so much.

user_13457410 · Answer

Let n be the array length. This loop is of worst-case running time O(n^2). The simple way to see this is as follows:

When next = 1, the number of operations done by the while loop is at most 1. When next = 2, the number of operations is at most 2, and so on until next = (n - 1). We can ignore the other operations done by the for loop because they constitute lower order terms which are irrelevant to growth.

So now, the number of operations is k * (1 + 2 + 3 + 4 + ... + (n - 1)) = k*(n*(n - 1)/2) = kn^2 - kn/2 where k is a constant factor.

Therefore, the growth of the function is of order n^2.

Edit:

To address the comment, we usually do not count the total number of statements because there is no standard to do so.

For example, would you count one iteration of the follow loop as one statement (a single print statement) or two statements (the print statement and incrementing i)?

for (int i = 0; i < n; i++)
{
    print(i);
}

In addition, it is frankly not a very useful metric. In most cases, we only care about the highest order term of an algorithm.

However, to answer your question, I would count the loop as performing these many statements: 2n^2 + 2n - 3.

Order and Growth Function of Loops

1 Answers