## 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

## 6 Comments

Bogo Sort.

This guy knows whats up!

Haha I hadn't heard of that one but I might cover it down the road.

Down the road as in the next article... *

glares at oaktree*I would like to see a tutorial on Bogo Sort.

Right on time! I was learning about algorithm complexity at my university the other day.

## Share Your Thoughts