Computing Algorithm Complexity - Confusion

Question

I have the following code snippet:

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

The complexity would be O(n^2), but if I want to dig a little more for the internal loop complexity then would it be (n (n-1))/2 or (n-1)!?

Answer 1

Constants are irrelevant as far as big-O notation is concerned.

Answer 2

Yes, O(n^2), but actually 0+1+...+n-1=n(n-1)/2 = O(n^2), definitely not (n-1)!

Answer 3

What you have calculated (n(n-1)/2) is the exact number of iterations for the code. When asked for time complexity in terms if big O, you give an estimate which is just big enough to express the time taken.

In other words, you need to find THE SMALLEST power of n such that for some k (k>0), k * n^power will be greater than the exact number of iterations. In your case, k happens to be 1 and power happens to be 2. Then O(n^power) is your time complexity.

Answer 4

time = n*(n-1)/2
     = (n*n - n)/2

Since big-O notation is an upper bound, the lesser order term (-n) and the constant factor (1/2) are both removed (because they aren't significant for representing the upper bound on time) to yield the big-O notation, O(n*n) better known as O(n^2).

Answer 5

First of all, (n-1)! means (n-1)(n-2)...(2)(1). This is clearly not what you want here.

If you count the actual number of iterations it's 0 + 1 + 2 + ... + (n-2) + (n-1). Note that there are n terms in the sum, and that we can pair them off in a way such that the average value of each pair is (n-1)/2. (Pair the highest and lowest, the second highest and second lowest, etc.) If n is odd, you'll have one left over that can't be paired, but conveniently its value is also (n-1)/2. Thus you have n terms and the average of all terms is (n-1)/2, so the total sum is n(n-1)/2.

Now, for big O notation it doesn't matter exactly how many iterations we have -- we just want to know the limit when n is very large. Note that our number of iterations can be written as (1/2)n^2 - (1/2)n. For very large n, the n^2 term is way, way bigger than the n term, so we drop the n term. That just leaves us with (1/2)n^2, but another rule of big O notation is we don't care about the constant factor, so we just write that it's O(n^2).

Answer 6

You could have an algorithm that runs in time

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

And it would still be O(n^2).

It's an open problem to find a better description for algorithm running time than O.