Big O Notation helps us determine how complex an operation is. It's of particular interest to the field of Computer Science. So for all you CS geeks out there here's a recap on the subject!
Big O notation cheat sheet. Big O notation is used to describe the complexity of an algorithm in terms of how well it scales. As a data set grows, so too can the number of cycles of processing timeand memory space requirements – this is known as scalability.
When you start delving into algorithms and data structures you quickly come across Big O Notation. It tells us how long an operation will take to run, as the size of the data set increases.
- Then the total runtime of the algorithm is O(1 + N + 1).You can use algebra rules inside of Big O Notation, so final algorithm’s performance is O(N + 2). If an algorithm takes O(f(N.
- C Data Structures and Algorithms Cheat Sheet Table of Contents 1.0 Data Structures 1.1 Overview 1.2 Vector std::vector 1.3 Deque std::deque 1.4 List std::list and std::forwardlist 1.5 Map std::map and std::unorderedmap 1.6 Set std::set 1.7 Stack std::stack 1.8 Queue std::queue 1.9 Priority Queue std::priorityqueue 1.10 Heap std::priority.
It's also a measure of complexity. The simple fact is that if something takes longer to run it is obviously more complex... logical eh? :)
Big O Notation
Here's a list of the more common Big O Notations from fastest (best) to slowest (worst).
| Notation | Description |
|---|---|
| O(1) | Constant: operations occur at the same speed no matter the size of the data set. ie. doing a null check |
| O(log n) | Logarithmic: operations take slightly longer as the size of the data set increases in orders of magnitude. Very close to O(1). ie. finding an item in a sorted data set using a binary search |
| O(n) | Linear: operations take longer in direct proportion to the size of the data set. ie. adding up all the values in data set |
| O(n log n) | Linearithmic: as the data set doubles in size, operations take longer by an increasing multiplier of one. ie. a quick sort |
| O(n2) | Quadratic: as the data set doubles in size, operations take four times longer. ie. two nested loops over a data set |
| O(2n) | Exponential: for every new element added to the data set operations take twice as long. ie. brute force attacking a password |
| O(n!) | Factorial: operations take n! times longer in direct proportion to the size of the data set. ie. calculating fibonacci numbers recursively |
They say a picture is worth a thousand words so this should help greatly with your understanding of the above :)
Conclusion
The key take away here is that if you are working with large data sets you need to be very careful when selecting the data structure and/or algorithm you use.
I'm going to be starting a new series on Data Structures soon which will reference these Big O notations. That'll help show the real world application of these theoretical concepts.
Until then... happy coding!
| Sorting Algorithms | Space complexity | Time complexity | ||
|---|---|---|---|---|
| Worst case | Best case | Average case | Worst case | |
| Insertion Sort | O(1) | O(n) | O(n2) | O(n2) |
| Selection Sort | O(1) | O(n2) | O(n2) | O(n2) |
| Smooth Sort | O(1) | O(n) | O(n log n) | O(n log n) |
| Bubble Sort | O(1) | O(n) | O(n2) | O(n2) |
| Shell Sort | O(1) | O(n) | O(n log n2) | O(n log n2) |
| Mergesort | O(n) | O(n log n) | O(n log n) | O(n log n) |
| Quicksort | O(log n) | O(n log n) | O(n log n) | O(n log n) |
| Heapsort | O(1) | O(n log n) | O(n log n) | O(n log n) |
| Data Structures | Average Case | Worst Case | ||||
|---|---|---|---|---|---|---|
| Search | Insert | Delete | Search | Insert | Delete | |
| Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
| Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
Big 0 Cheat Sheet
| n f(n) | log n | n | n log n | n2 | 2n | n! |
|---|---|---|---|---|---|---|
| 10 | 0.003ns | 0.01ns | 0.033ns | 0.1ns | 1ns | 3.65ms |
| 20 | 0.004ns | 0.02ns | 0.086ns | 0.4ns | 1ms | 77years |
| 30 | 0.005ns | 0.03ns | 0.147ns | 0.9ns | 1sec | 8.4x1015yrs |
| 40 | 0.005ns | 0.04ns | 0.213ns | 1.6ns | 18.3min | -- |
| 50 | 0.006ns | 0.05ns | 0.282ns | 2.5ns | 13days | -- |
| 100 | 0.07 | 0.1ns | 0.644ns | 0.10ns | 4x1013yrs | -- |
| 1,000 | 0.010ns | 1.00ns | 9.966ns | 1ms | -- | -- |
| 10,000 | 0.013ns | 10ns | 130ns | 100ms | -- | -- |
| 100,000 | 0.017ns | 0.10ms | 1.67ms | 10sec | -- | -- |
| 1'000,000 | 0.020ns | 1ms | 19.93ms | 16.7min | -- | -- |
| 10'000,000 | 0.023ns | 0.01sec | 0.23ms | 1.16days | -- | -- |
| 100'000,000 | 0.027ns | 0.10sec | 2.66sec | 115.7days | -- | -- |
| 1,000'000,000 | 0.030ns | 1sec | 29.90sec | 31.7 years | -- | -- |