What is the n in O(n) when comparing sorting algorithms?

Posted by Mumfi on Stack Overflow See other posts from Stack Overflow or by Mumfi
Published on 2014-05-31T21:15:37Z Indexed on 2014/05/31 21:26 UTC
Read the original article Hit count: 161

Filed under:
|

The question is rather simple, but I just can't find a good enough answer. I've taken a look at the most upvoted question regarding the Big-Oh notation, namely this:

Plain English explanation of Big O

It says there that:

For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering).

Now let's consider the simple bubble sort algorithm:

for (int i = arr.length - 1; i > 0 ; i--) {
        for (int j = 0; j<i; j++) {
            if (arr[j] > arr[j+1]) {
                switchPlaces(...)
            }
        }
    }

I know that worst case is O(n^2) and best case is O(n), but what is n exactly? If we attempt to sort an already sorted algorithm (best case), we would end up doing nothing, so why is it still O(n)? We are looping through 2 for-loops still, so if anything it should be O(n^2). n can't be the number of comparison operations, because we still compare all the elements, right?

This confuses me, and I appreciate if someone could help me.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about time-complexity