Welcome back, 0x00sec community, to my series on sorting.
I introduced in my last article the concept of complexity. When I say complexity, I’m talking about time complexity.
What Is Time Complexity?
You can view the Wikipedia article here, but I’ll be speaking from my heart and soul.
Time complexity is a mathematical representation of how long an algorithm could take in the worse-case scenario, and it is a function of the size of the input. Input size is usually represented by n.
Example: Bubble Sort in C++
Alright, class. Take out that C++ code I handed out yesterday…
void bubblesort(vector<char>& vec) {
int n = vec.size();
// nest loops because O(n^2)
// changes_made is an optimization that can reduce runtime in certain conditions
bool changes_made = false;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1; j++) {
if (vec[j] > vec[j+1]) {
// swap them
char temp = vec[j];
vec[j] = vec[j+1];
vec[j+1] = temp;
// tell program to run thru vec at least once more
changes_made = true;
}
}
// optimization to exit loop if no changes made
if (!changes_made) break;
changes_made = false;
}
}
Now, let’s go line-by-line in bubblesort(...) and add up all the things we have to do.
- On line 9, we declare a variable to hold the size of our vector, so let’s add
1to our complexity. - Another variable is declared on line 13, so now our complexity is
2. - We have a
forloop starting on line 15, so that addsn-1to our complexity, because we loop through the vector from the first element to the second-to-last. We have aforloop within the outer one in which we do the same, so we have(n-1)x(n-1). Our grand total is(n-1)x(n-1)+2. We do some things in theforloops, but we can ignore those and you’ll see why in a second. - Okay, now we’ll simplify down our total:
n^2 - 2n + 1 + 2 = n^2 -2n +3 - Let’s take the limit as n approaches infinity. This is a calculus thing, but it basically means that we want to see what happens as the size of our vector gets really, really big.
- Per the limit operation, we can simplify it down to n^2, but note that any coefficient of n^2 can also be stripped, since no coefficient could really do all that much to the square of infinity.
Complexity Notation
Okay, so now we’ve concluded that the time complexity of our algorithm, Bubble Sort, can be expressed as n^2. But what if the vector was already sorted? Due to our awesome optimization, per changes_made, we only need n time to sort (in this best-case situation).
That means that our algorithm has a lower bound time complexity of n and an upper bound time complexity of n^2.
How do we express upper and lower bounds?
Upper bound notation is expressed as O(n^2) for our algorithm. This is called “Big-O Notation.” To reiterate, this notation represents the worst-case-input scenario for our algorithm as n gets really, really huge.
Lower bound notation is expressed using the Greek letter omega, O. We say the lower-bound, the best-case, for our algorithm (Bubble Sort) is O(n).
Conclusion
Well, that’s time complexity right there. Bubble sort has O(n^2) and O(n) time complexity. From now on, I’ll be noting the time complexity for each algorithm I discuss in the Sorting series.
Best,
oaktree