Image source

So why does it matter which algorithm your program uses? As long as it gets the job done, isn't it fine? This is actually not the case at all. Some algorithms are a lot slower than others. This makes a huge difference when dealing with very large amounts of data. So how can we measure this?

Big Oh

Big Oh is a way of measuring the speed of a program on a large scale. Take a look at this C++ program segment:

int a = 4;
int b = 5;
cout << a + b;

This section will always run the same no matter what. It has 3 lines. We could say the complexity of this program is 3. In terms of Big Oh, this would be an O(1) complexity. The reason for this is because Big Oh doesn't care about the literal complexity of a program. When we have a program with the complexity of 3xO(n^2) and one with 300xO(n^2), the 3 and 300 become very insignificant when n is billion. These both just break down to simply O(n^2). This makes analyzing the speed of a program much easier. Also, when the complexity of a program is O(n) + O(n^2), we just call it O(n^2). For the sake of simplicity, we only care about the largest Big Oh.

Take a look at this program segment:

for(int x = 0; x < n; x++)
    cout << x + y;

This loop executes n times. This is categorized under O(n).

now take a look at this program segment:

for(int x = 0; x < n; x++)
    for(int y = 0; y < n; y++)
        cout << x + y;

These are two nested loops. The second loop executes n times multiplied by the number of times that the first loop executes, which is also n. This means that the Big Oh comes out to O(n^2). Do you see the pattern? For 3 nested loops, the Big Oh would be O(n^3), and so on. For the powers beyond O(n^3), the Big Oh is simply just O(2^n). This is for simplicity. Anything such as O(n^4), O(n^5), O(n^6)... are so terrible that they are just lumped in with O(2^n) category.

Here is the list of Big Oh complexity. The list goes from faster on top to slower on bottom.

O(1)
O(logn)
O(n)
O(nlogn)
O(n^2)
O(n^3)
O(2^n)
O(n!)
O(n^n)

So when programming, it is best to shoot for the lowest possible Big Oh for your program.

Click here for a very useful website on Big Oh.

A Real Life Example

A while ago, I wrote a program that could solve the traveling salesman problem. Here is the problem:

A salesman needs to visit n cities, once each. Given a list of the prices of flights from each city to another, calculate the cheapest route.

The only way to find the cheapest route every single time is to test every possible path and compare them all. This comes out to a Big Oh of O(n!). It is absolutely terrible! Here is some sample output of my program. I used the time command on a Linux system to calculate how long the program was running. The number after "input" indicates how many cities each input file contains.

[cmw4026@omega TSP]$ gcc tsp.c
[cmw4026@omega TSP]$ time ./a.out < input5
The tour  1 - 2 - 3 - 4 - 5 - 1 costs: 10500

real    0m0.001s
user    0m0.000s
sys     0m0.001s
[cmw4026@omega TSP]$ time ./a.out < input10
The tour  1 - 8 - 4 - 2 - 3 - 7 - 6 - 5 - 10 - 9 - 1 costs: 2000

real    0m0.202s
user    0m0.200s
sys     0m0.001s
[cmw4026@omega TSP]$ time ./a.out < input11
The tour  1 - 8 - 7 - 5 - 2 - 3 - 4 - 6 - 10 - 9 - 11 - 1 costs: 1972

real    0m3.365s
user    0m2.257s
sys     0m0.001s
[cmw4026@omega TSP]$ time ./a.out < input12
The tour  1 - 8 - 6 - 7 - 5 - 4 - 2 - 10 - 3 - 9 - 11 - 12 - 1 costs: 1644

real    0m55.419s
user    0m27.915s
sys     0m0.012s
[cmw4026@omega TSP]$

The time it took to run this program jumped from 3 to 55 seconds when I added only one more element! As you can see, O(n!) is an absolutely horrible Big Oh for a program to have!

Want to see the time for 13 cities (elements)?

The tour  1 - 11 - 4 - 8 - 2 - 10 - 7 - 6 - 3 - 9 - 13 - 5 - 12 - 1 costs: 1811

real    15m53.206s
user    6m53.345s
sys     0m0.423s
[cmw4026@omega TSP]$

15 minutes!!! I'm going to have to stop here!

I hope this helped! Leave any suggestions in the comments!

---

Be sure to check out my programming tutorial series of you liked this post. It goes over mostly C++, but also C and some basics that can be applied to most languages. Here is the series up to date:

Part 1: Hello World!

Part 2: Variables

Part 3: Functions

Part 4: if(), else, else if()

Part 5: Loops

Part 6: Arrays

Part 7: Basic Input/Output

Part 9: Sorting Arrays

Part 10: Random Numbers

Part 11: Colored Text in your Terminal

Part 12: Recursion

Part 13: Binary Search

Part 14: 2D Arrays

Part 15: String Processing

Part 16: Binary, Bitwise Operators, and 2^n

Part 17: Pointers

Part 18: Pointer Arithmetic

Part 19: Object Oriented Programming 1 -- Data Structures

Part 20: Object Oriented Programming 2 -- Classes

Part 21: Object Oriented Programming 3 -- Polymorphism

Part 22: Command Line Arguments

Part 23: Header Files

Part 24: Programming in separate files

Part 25: File I/O

Part 26: Threading and concurrency

Part 27: Converting Decimal to Binary and Hexidecimal

---