BigO (time complexity) Made Simple

Here “Elements” is referring to the in put size, and “Operations” is referring to the time the algorithm takes https://www.bigocheatsheet.com/

What is it?

BigO is a way to grade the efficiency* of our algorithm** relative to the input size. A “Excellent” solution is one that is not effected by the input size. A “Horrible” solution is one that takes a lot longer as the size of the input grows by a small amount.

*BigO time complexity looks at how fast/slow an algorithm runs, however BigO space complexity will look at storage size to measure efficiency.

**instructions designed to perform a specific task

Why is it used?

• Creates a standard to evaluate efficiency of code
• Machine Independent: run time might differ depending on the device, BigO creates a more consistent grading method
• Helps identify inefficient points of code

How does it work?

• Ignores the details, and looks at the big trends
• Looks at Worst Case and tends to ignore Best Case and Average Case

Our Example: In this example our input is a playlist. The playlist is an array of songs. Our algorithm is responsible for playing a song.

Constant O(1)= EXCELLENT 🌟🌟🌟🌟🌟💯

• Example “Algorithm”: Plays the first song on the playlist.
• Worst case: No matter the size of the playlist our algorithm will take the same amount of time to find the first song.
• Popular Algorithms: Hashing
• Note: Constant time is not always the best/simplest solution. The takeaway is that no matter the size of the input it will always take the same time to execute. So it is optimal in regards to BigO time complexity.

Constant O(1)

Logarithmic O(log n)= EXCELLENT/GOOD 🌟🌟🌟🌟🌟

• Example “Algorithm”: Plays “Levitating”. With an alphabetically sorted playlist, we can narrow our list down. First we scroll quickly down to “Put a Light On”(the middle point in the playlist), however “L” comes before “P”. Therefore we scroll back up to “Drift”(to the middle of the upper half of the alphabet), “D” comes before “L” so we know we have to scroll down. We scroll down and now found “Levitating” (the middle point of our shortened list)!
• Worst case: We will need to search through part of the playlist every time, but not the entire playlist. So when the size of the playlist grows the search time will grow, however the growth will be small.
• Popular Algorithms: Binary Search (must be sorted)

Logarithmic O(log n)

Linear O(n)= FAIR 🌟🌟🌟

• Example Algorithm: Plays “Vanille Fraise”. The playlist is not sorted, therefore we will look at every single song on the playlist until we see “Vanille Fraise”.
• Worst case: Since the playlist is not sorted “Vanille Fraise” might be the last song. Therefore we will have to look at every single song on the playlist.
• Popular Algorithms: Linear Search, Depth First Search, Breadth First Search (search algorithms visit every element in the list, because the list is not sorted)

Linear O(n)

Linearithmic O(n log n)= BAD 👎

• Example Algorithm: Go through entire playlist to choose a song. We decide to listen to “Levitating”, but keep looking . We go back through the playlist. This time the playlist is sorted and can find the song more easily. (combining O(n) + O(log n))
• Worst case: On our first search we will need to look through the entire playlist. On our second search we will only go through part of the playlist since it is now sorted.
• Popular Algorithms: Merge Sort, Quick Sort
• Note: “good/best” efficiency for sorting unordered lists

Linearithmic O(n log n)

Quadratic O(n²)(Polynomial)= HORRIBLE 👎👎

• Example Algorithm: Go through entire playlist to choose a song. We decide to listen to “Levitating”, but keep looking . Playlist is not sorted so we go through the entire list again until we find the “Levitating”. (performing O(n)twice)
• Worst case: Since both times the list is not sorted, we will go through entire playlist twice.
• Popular Algorithms: Bubble Sort, Insertion Sort, Selection Sort

The below are also worth mentioning, however the examples don’t work as well.

Cubic O(n³)(Polynomial)= HORRIBLE 👎👎

• Example: Going through the entire playlist three times.
• Popular Algorithms: Dynamic Programing

Exponential O(C^ n)= HORRIBLE 👎👎👎

• Example: Every time you add a song to the playlist, every song previously added multiplies by the new number of new songs on the playlist….
• Popular Algorithms: Subsets

Factorial O(N!)= HORRIBLE

• Example: Calculate every possible order the playlist might play in
• Popular Algorithms: Permutation, Traveling Salesman