We created this Big O Cheat Sheet initially for students of Master the Coding Interview: Data Structures + Algorithms (my Coding Interview Bootcamp course) but we're now sharing it with any and all Developers that want to learn and remember the basics of Big O.
Enter your email below and we'll send it to you 👇
Unsubscribe anytime.
If you’ve stumbled across this page and are just starting to learn Big O, nice work! Big O is one of the most important topics for any software developer or engineer.
Even if (... when!) you're coding 10 years from now, this is a topic that will be around for a long time and will make you a better developer. This was true for me and will be for you as well.
Many of the biggest tech companies (Google, Amazon, Facebook... aka Meta, etc.) ask questions about Big O as part of their coding interview process for good reason.
That said, if you're currently stuck in an endless cycle of YouTube tutorials and not having success getting hired as a developer at the company of your dreams, I can help.
Come join the Zero To Mastery Academy and take my Ultimate Coding Interview Bootcamp.
You'll not only learn data structures and algorithms (and Big O) but also the exact steps to take to get more interviews, more job offers, and a higher salary.
I've also made the entire Big O introduction section of my Coding Interview Bootcamp completely free (no signup or credit card necessary) so that you can learn more about Big O for free.
You can also watch it on Youtube right here 👇
Please enjoy this cheatsheet and if you'd like to submit any corrections or suggestions, feel free to email us at support@zerotomastery.io
O(1) Constant - no loops
O(log N) Logarithmic - usually searching algorithms have log n if they are sorted (Binary Search)
O(n) Linear - for loops, while loops through n items
O(n log(n)) Log Linear - usually sorting operations
O(n^2) Quadratic - every element in a collection needs to be compared to ever other element. Two nested loops
O(2^n) Exponential - recursive algorithms that solves a problem of size N
O(n!) Factorial - you are adding a loop for every element
Iterating through half a collection is still O(n)
Two separate collections: O(a * b)
| Big O | Name | Description |
|---|---|---|
| 1 | Constant | statement, one line of code |
| log(n) | Logarithmic | Divide and conquer (binary search) |
| n | Linear | Loop |
| n*log(n) | Linearithmic | Effective sorting algorithms |
| n^2 | Quadratic | Double loop |
| n^3 | Cubic | Triple loop |
| 2^n | Exponential | Complex full search |
+,-, \*, /)<, >, ===)for, while)function())| Sorting Algorithms | Space complexity | Time complexity | Time complexity |
|---|---|---|---|
| Worst case | Best case | Worst case | |
| Insertion Sort | O(1) | O(n) | O(n^2) |
| Selection Sort | O(1) | O(n^2) | O(n^2) |
| Bubble Sort | O(1) | O(n) | O(n^2) |
| Mergesort | O(n) | O(n log n) | O(n log n) |
| Quicksort | O(log n) | O(n log n) | O(n^2) |
| Heapsort | O(1) | O(n log n) | O(n log n) |
| Worst Case→ | Access | Search | Insertion | Deletion | Space Complexity |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | N/A | O(n) | O(n) | O(n) | O(n) |
Rule 1: Always worst Case
Rule 2: Remove Constants
Rule 3:
O(a + b).O(a * b)+ for steps in order
* for nested steps
Rule 4: Drop Non-dominant terms