Sorting (Part 2.0): A Tangent to Time Complexity

Welcome back, NB 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... Well, really just click this link or look at the screenshot below:

So, let's analyze this code. Again, let's ignore the main() function because that's just where we take input. If you're confused, I did main() from the screenshot.

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 1 to our complexity.
• Another variable is declared on line 13, so now our complexity is 2.
• We have a for loop starting on line 15, so that adds n-1 to our complexity, because we loop through the vector from the first element to the second-to-last. We have a for loop 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 the for loops, 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.

Do me a favor and comment the sorting algorithm you want me to discuss most immediately. Your choices are selection sort and insertion sort, because of their... time complexities.

Best,
oaktree