Is the Big-O of this program O(N^2)?

Question

I am reading Cracking the Coding Interview (the new one). The program seems to be running correctly. When I check it out though, it seems N^2 / 2 is the answer. I don't think I am right. Could someone tell me what the Big-O is and why?

    class Program
    {
        static void Main(string[] args)
        {
            int userNumber = Convert.ToInt32(Console.ReadLine());
            int[] makeAnArray = new int[userNumber];
            for (var x = 0; x < userNumber; x++)
            {
                makeAnArray[x] = x; 
            }
            DisplayIterations(makeAnArray);
        }
        static void DisplayIterations(int[] testA)
        {
            int totalIterations = 0;
            for (var i = 0; i < testA.Length; i++)
            {
                totalIterations++;
                Console.WriteLine("i is " + i );
                for (var j = i + 1; j < testA.Length; j++)
                {
                    totalIterations++;
                    Console.WriteLine("j is " + j);
                }
            }
            Console.WriteLine("The amount of iterations: " + totalIterations);
        }
    }

Basically the function takes in an array, runs a for loop for the array length and a for loop length-1. I put in 10 I get 55 back.

Answer 1

The actual number of iterations, where n is the size of the array, is:

n(n+1)/2

Which can be expanded to

(n^2 + n)/2

However, in Big O notation, you are generally interested in the class of algorithm as input sizes become large, and can ignore both constants (such as the 2 in the above formula) as well as variables with a lesser exponent than the largest - therefore you can ignore the n component because n^2 will very, very quickly outweigh the non-quadratic component as n increases in size. Therefore, you would call an algorithm with actual operation count of (n^2 + n)/ 2 simply as O(n^2).

For reference, here is the definition of Big O notation from Wikipedia:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Explanation of why you have n(n+1)/2 operations:

You are iterating over your array in the following manner:

for (var i = 0; i < arr.Length; i++)
{
    for (var j = i + 1; j < arr.Length; j++)
    {
    }
}

I'm going to draw out a few examples with the following notation:

i0 means that your program printed out 'i is 0'
j1 means that your program printed out 'j is 1'

Let's draw out what your program would print with an array length of 1, where each row represents an entire iteration of the outer loop as well as the inner loop:

i0

Now with an array length of 3:

i0 j1 j2
i1 j2
i2

With an array length of 6:

i0 j1 j2 j3 j4 j5
i1 j2 j3 j4 j5
i2 j3 j4 j5
i3 j4 j5
i4 j5
i5

What you can easily see by drawing it out this way is that we are printing out 6 + 5 + 4 + 3 + 2 + 1 statements when n = 6. Note that that is just the addition of all integers from 1 to 6, or more generically, from 1 to n. The commonly known formula for the sum of integers from 1 to n is (surprise!) (n^2 + n)/2.

I typed this out a little hastily but hopefully you see how I arrived at this. This agrees with your assessment that for an input of length 10, you have 55 iterations: (10^2 + 10)/2 = (110)/2 = 55.

Answer 2

Yes, the Big-O of that program is O(N^2).

In Big-O notation you only use the dominant factors (e.g. ignore coefficients).

So, even though you are more precise (actual answer is n(n-1)/2), the notation ignores your 1/2 coefficient & any factors less than n^2, which is the dominant factor.

See this answer: Why do we ignore co-efficients in Big O notation?