What is the n in big-O notation?
algorithm, big-o, complexity-theory, time-complexity
Solution
`n` is usually the size of the input. For array, that would be the number of elements.
To see the different cases, you would need to change the algorithm:
for (int i = arr.length - 1; i > 0 ; i--) {
boolean swapped = false;
for (int j = 0; j<i; j++) {
if (arr[j] > arr[j+1]) {
switchPlaces(...);
swapped = true;
}
}
if(!swapped) {
break;
}
}
Your algorithm's best/worst cases are both `O(n^2)`, but with the possibility of returning early, the best-case is now `O(n)`.
Problem
The question is rather simple, but I just can't find a good enough answer. On the most upvoted SO question regarding the big-O notation, it says 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²)` 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²)`. `n` can't be the number of comparison operations, because we still compare all the elements, right?