# 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

• Hot
• Latest