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

**Want to start making money as a white hat hacker?** Jump-start your hacking career with our 2020 Premium Ethical Hacking Certification Training Bundle from the new Null Byte Shop and get over 60 hours of training from cybersecurity professionals.

Other worthwhile deals to check out:

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