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
algorithm
|time-complexity
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