Big-O Notation Cheat Sheet: Time, Space, Graphs & Interview Tables
A big o notation cheat sheet is a compact reference for comparing how an algorithm’s running time and memory usage grow as input size increases. It matters because a solution that works for 1,000 UPI transactions may fail at 10 crore records; after reading, you can choose, compare, and justify algorithms under real constraints.
Big-O sits at the centre of data structures, algorithms, database indexing, distributed systems, and performance engineering. Intermediate and advanced learners use it to estimate scalability before writing code, especially when production traffic, memory limits, or interview constraints make brute force unacceptable.
You will be able to read a time complexity graph, identify time and space complexity from code, revise standard algorithm complexities, and answer interview questions with precise reasoning instead of memorised labels.
Core Concepts
Big-O notation describes asymptotic growth, not exact runtime in milliseconds. To use this cheat sheet well, separate three ideas: the mathematical bound, the algorithmic operation being counted, and the input model. For example, scanning Aadhaar verification logs is linear in the number of logs, while looking up a payment ID in a well-sized hash table is expected constant time.
1.Asymptotic Notation
Big-O, Omega, Theta, little-o, and little-omega are not interchangeable. Big-O gives an upper bound, Omega gives a lower bound, and Theta gives a tight bound. Little-o and little-omega are stricter comparisons used in proofs, especially when showing that one growth rate is definitely smaller or larger than another.
A familiar example is an IRCTC train search page. If the system scans every train route to find matches, the operation is O(n). If it uses a sorted index and binary search, the lookup can be O(log n). In a banking fraud-detection pipeline, a nested comparison of every transaction against every other transaction is O(n²), while grouping by account ID first can reduce repeated work.
Interviewers usually expect the simplest valid asymptotic answer after dropping constants and lower-order terms. If code performs 3n + 20 primitive operations, the complexity is O(n), not O(3n) or O(n + 20). If code performs n² + n log n, the dominant term is O(n²).
Code Example
2.Complexity Classes
The most useful time complexity cheat sheet starts with growth classes. O(1) is constant, O(log n) is logarithmic, O(n) is linear, O(n log n) is linearithmic, O(n²) and O(n³) are polynomial, and O(2ⁿ) or O(n!) are exponential or factorial. The jump from O(n log n) to O(n²) is often the difference between passing and timing out.
For a familiar Indian example, checking whether a PAN number exists in a hash set is expected O(1), while searching an unsorted list of PAN records is O(n). In healthcare analytics, sorting patient lab reports by timestamp is usually O(n log n), but comparing every patient with every other patient for similarity becomes O(n²).
A time complexity graph plots input size on the x-axis and operation count on the y-axis. O(log n) grows slowly, O(n) grows steadily, O(n²) bends upward sharply, and O(2ⁿ) becomes unusable very quickly. Such graphs help explain why a technically correct brute-force solution can still be impractical.
| Complexity | Name | Common Algorithms | Practical Meaning |
|---|---|---|---|
| O(1) | Constant | Array index access, stack push, hash lookup average case | Work does not grow with input size |
| O(log log n) | Double logarithmic | Some integer search structures and specialised algorithms | Extremely slow growth, less common in interviews |
| O(log n) | Logarithmic | Binary search, balanced BST lookup, heap height operations | Input is repeatedly halved or reduced by a factor |
| O(sqrt n) | Square-root | Trial division up to square root, block decomposition query blocks | Often appears in number theory and decomposition |
| O(n) | Linear | Array scan, BFS over vertices only, counting frequency | Each item is processed a constant number of times |
| O(n log n) | Linearithmic | Merge sort, heap sort, average quicksort, efficient comparison sorting | Typical best practical bound for general comparison sorting |
| O(n²) | Quadratic | Bubble sort, selection sort, insertion sort worst case, pair comparison | Nested loops over the same input |
| O(n³) | Cubic | Floyd-Warshall, naive matrix multiplication | Often acceptable only for small n |
| O(2ⁿ) | Exponential | Subset generation, naive Fibonacci recursion | Each extra item can double the work |
| O(cⁿ) | General exponential | Many brute-force search and branching algorithms | Growth depends on branching factor c |
| O(n!) | Factorial | Permutation generation, brute-force travelling salesperson | All possible orderings are explored |
| O(nⁿ) | Super-exponential style growth | Naive assignment of n choices to n positions | Usually infeasible beyond tiny inputs |
Code Example
3.Analysis Rules
Complexity analysis follows a few repeatable rules. Sequential blocks add, nested loops multiply, independent input sizes must be named separately, and recursive algorithms usually require a recurrence. A loop from 1 to n is O(n); a loop that doubles the counter each time is O(log n); two nested n-sized loops are O(n²).
For a familiar example, validating all items in one Zomato cart is O(n), but checking every item against every available coupon can become O(nm), where n is items and m is coupons. In SaaS analytics, processing users and events separately is O(u + e), while joining every user with every event naively is O(ue).
Amortised complexity is another standard interview topic. Dynamic arrays may occasionally resize in O(n), but a long sequence of appends is O(1) amortised per append. Hash tables also rely on amortised reasoning when resizing and rehashing are spread across many operations.
Code Example
4.Searching Algorithms
Searching complexity depends mainly on whether the data is ordered and whether direct addressing is available. Linear search is O(n) because it may inspect every element. Binary search is O(log n), but only when the data is sorted and random access is efficient. Hash lookup is expected O(1), but worst-case O(n) if many keys collide.
A familiar example is finding one mobile number in an unsorted contact export, which is linear search. Searching a sorted list of railway station codes can use binary search. In banking systems, retrieving a transaction by ID from a hash index is expected constant time, while range queries such as transactions between two timestamps are better served by balanced trees or database indexes.
| Algorithm | Best | Average | Worst | Space | Requirement |
|---|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) | No ordering required |
| Binary search | O(1) | O(log n) | O(log n) | O(1) iterative, O(log n) recursive | Sorted random-access data |
| Jump search | O(1) | O(sqrt n) | O(sqrt n) | O(1) | Sorted random-access data |
| Interpolation search | O(1) | O(log log n) | O(n) | O(1) | Sorted and near-uniform distribution |
| Exponential search | O(1) | O(log i) | O(log i) | O(1) | Sorted unbounded or large array, target at index i |
| Hash table lookup | O(1) | O(1) expected | O(n) | O(n) | Good hashing and load factor |
Code Example
5.Sorting Algorithms
Sorting is one of the most tested areas because several algorithms solve the same problem with different trade-offs. Bubble, selection, and insertion sort are simple but usually O(n²). Merge sort and heap sort guarantee O(n log n). Quicksort is O(n log n) on average but O(n²) in the worst case without good pivot handling.
Non-comparison sorts have different constraints. Counting sort is O(n + k), where k is the key range. Radix sort is O(d(n + b)), where d is the number of digits and b is the base or bucket count. Bucket sort can be O(n + k) on average when data is uniformly distributed, but it can degrade if buckets become uneven.
A familiar example is sorting UPI transactions by amount for a monthly statement. For arbitrary amounts, merge sort or quicksort-style sorting is reasonable. In an ed-tech platform sorting exam scores from 0 to 100, counting sort can be excellent because the range is small and known.
| Sorting Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) with early stop | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No by default |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) average stack | No by default |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes if implemented carefully |
| Radix sort | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | Yes with stable inner sort |
| Bucket sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Depends on bucket sorting |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Code Example
6.Data Structures
Data structure complexity is about operation cost: access, search, insert, delete, peek, enqueue, dequeue, and resize. Arrays provide O(1) index access but costly middle insertion. Linked lists support O(1) insertion if the node reference is known, but O(n) search. Hash tables provide expected O(1) lookup, insert, and delete, with O(n) worst case under collisions.
A familiar example is storing recent OTP attempts in a stack-like structure where push and pop are O(1). In e-commerce inventory systems, product ID to stock count is usually a hash map because expected lookup is O(1). For ordered leaderboard queries in gaming or ed-tech, a balanced tree is better than a plain hash map because it supports sorted traversal.
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Static array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Dynamic array | O(1) | O(n) | O(1) amortised append, O(n) middle | O(n) | O(n) |
| Singly linked list | O(n) | O(n) | O(1) at head or known node | O(1) with previous reference, otherwise O(n) | O(n) |
| Doubly linked list | O(n) | O(n) | O(1) at known node | O(1) at known node | O(n) |
| Stack | O(n) | O(n) | O(1) push | O(1) pop | O(n) |
| Queue | O(n) | O(n) | O(1) enqueue | O(1) dequeue | O(n) |
| Deque | O(n) | O(n) | O(1) at both ends | O(1) at both ends | O(n) |
| Hash table | Not index based | O(1) expected, O(n) worst | O(1) expected, O(n) worst | O(1) expected, O(n) worst | O(n) |
Code Example
7.Trees And Heaps
Tree complexity depends on height. A balanced binary search tree has height O(log n), so search, insert, and delete are O(log n). A skewed BST can degrade to O(n). Heaps support fast minimum or maximum access in O(1), insertion in O(log n), and extract-min or extract-max in O(log n).
A familiar example is autocomplete suggestions stored in a trie, where lookup depends on word length rather than total number of words. In food delivery dispatch, a priority queue can assign the nearest or highest-priority order by repeatedly extracting the best candidate in O(log n). In file systems and compilers, trees are also used for hierarchical and syntax representations.
| Structure | Search | Insert | Delete | Min or Max | Space |
|---|---|---|---|---|---|
| Unbalanced BST | O(h), worst O(n) | O(h), worst O(n) | O(h), worst O(n) | O(h) | O(n) |
| AVL tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Red-black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Binary heap | O(n) | O(log n) | O(log n) extract root | O(1) root access | O(n) |
| Trie | O(L) | O(L) | O(L) | Not applicable | O(total characters) |
| B-tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
Code Example
8.Graph Algorithms
Graph complexity is usually expressed with V for vertices and E for edges. BFS and DFS are O(V + E) with adjacency lists because every vertex and edge is processed a bounded number of times. With an adjacency matrix, scanning neighbours can cost O(V²), even if the graph has few edges.
Shortest path and spanning tree algorithms depend on data structures. Dijkstra with a binary heap is commonly O((V + E) log V). Bellman-Ford is O(VE) and handles negative edge weights. Floyd-Warshall is O(V³) and is useful for all-pairs shortest paths on smaller dense graphs. Kruskal is O(E log E), while Prim is often O(E log V) with a heap.
A familiar example is metro route planning where stations are vertices and tracks are edges. In logistics, warehouses, delivery hubs, and road segments form weighted graphs for route optimisation. In social networks, friend recommendations often use graph traversal and neighbourhood expansion.
| Graph Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path in unweighted graphs, level traversal |
| DFS | O(V + E) | O(V) | Connectivity, cycle detection, topological traversal |
| Topological sort | O(V + E) | O(V) | Dependency ordering in DAGs |
| Dijkstra with binary heap | O((V + E) log V) | O(V + E) | Non-negative weighted shortest paths |
| Bellman-Ford | O(VE) | O(V) | Shortest paths with negative edges |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest paths |
| Kruskal MST | O(E log E) | O(V) | Minimum spanning tree using sorting and DSU |
| Prim MST with heap | O(E log V) | O(V + E) | Minimum spanning tree from a start vertex |
| Union-Find operations | Almost O(1), inverse Ackermann amortised | O(V) | Connectivity and Kruskal MST |
Code Example
9.Dynamic Programming
Dynamic programming complexity is usually the number of states multiplied by the transition cost per state. Memoisation stores solved subproblems in a cache, while tabulation fills a table iteratively. DP often converts exponential recursion into polynomial time by avoiding repeated work.
A familiar example is calculating the number of ways to climb steps, where naive recursion repeats the same calls exponentially. A fintech example is computing optimal repayment schedules under constraints, where each state may represent month, balance, and decision choice. In recommendation systems, sequence alignment and edit distance use DP over two dimensions.
Common DP complexities include O(n) for one-dimensional recurrence, O(nW) for 0/1 knapsack with capacity W, O(n²) for longest increasing subsequence DP, O(nm) for edit distance, and O(n³) for matrix chain multiplication. Optimised variants may reduce space from O(nm) to O(min(n, m)) when only the previous row is needed.
| DP Problem | Typical Time | Typical Space | State Idea |
|---|---|---|---|
| Fibonacci with memoisation | O(n) | O(n) | n |
| Climbing stairs | O(n) | O(1) optimised | current step |
| 0/1 knapsack | O(nW) | O(nW) or O(W) | item index and capacity |
| Edit distance | O(nm) | O(nm) or O(min(n, m)) | prefix lengths |
| Longest common subsequence | O(nm) | O(nm) | two prefix lengths |
| Longest increasing subsequence DP | O(n²) | O(n) | best ending at index |
| LIS with binary search | O(n log n) | O(n) | minimum tail values |
| Matrix chain multiplication | O(n³) | O(n²) | interval boundaries |
Code Example
10.Backtracking And Recursion
Backtracking explores choices, undoing a choice when it cannot lead to a valid solution. Its complexity is often exponential or factorial because the algorithm walks a search tree. The exact bound depends on the number of choices at each level and the depth of the decision tree.
A familiar example is generating all possible PIN patterns under constraints; each extra digit increases the search space. In travel planning, brute-forcing every city order for a small travelling salesperson variant is O(n!), because it checks permutations. In scheduling systems, assigning slots to sessions can become exponential when every session has multiple valid rooms and times.
Recursion also adds space complexity through the call stack. A depth-n recursion uses O(n) stack space even if it stores no extra array. Backtracking may additionally store the current path, visited flags, and result list; if all solutions are stored, output size can dominate memory.
Code Example
11.String Algorithms
String complexity depends on length, alphabet size, and whether repeated comparisons are avoided. Naive substring search can be O(nm), where n is text length and m is pattern length. KMP preprocesses the pattern and searches in O(n + m). Rabin-Karp is expected O(n + m), but hash collisions can cause O(nm) worst case.
A familiar example is searching for a train number inside a long SMS inbox export. Naive search may be fine for tiny text, but indexing or KMP-style scanning matters at scale. In cybersecurity, scanning logs for attack signatures benefits from efficient string matching because the same patterns are checked across millions of lines.
| String Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| Naive pattern search | O(nm) | O(1) | Small text or simple implementation |
| KMP | O(n + m) | O(m) | Deterministic substring search |
| Rabin-Karp | O(n + m) expected, O(nm) worst | O(1) | Multiple pattern matching with hashing |
| Z algorithm | O(n + m) | O(n + m) | Pattern matching and prefix analysis |
| Trie prefix search | O(L) | O(total characters) | Autocomplete and dictionary prefixes |
| Suffix array construction | O(n log n) common implementations | O(n) | Fast substring queries after preprocessing |
Code Example
12.Number Theory
Number theory complexities often depend on the value of n, not just the number of input items. Checking primality by trying every divisor up to n is O(n), but trying only up to square root is O(sqrt n). Euclid’s GCD algorithm is O(log min(a, b)) because remainders shrink quickly.
A familiar example is validating simple divisibility rules for invoice numbers, where modulus operations are constant-time for typical machine-sized integers. In cryptography and security systems, modular exponentiation matters because naive repeated multiplication is too slow; fast exponentiation runs in O(log exponent) multiplications.
| Algorithm | Time Complexity | Space Complexity | Common Use |
|---|---|---|---|
| Euclidean GCD | O(log min(a, b)) | O(1) iterative | Fractions, modular arithmetic |
| Trial division primality | O(sqrt n) | O(1) | Basic primality check |
| Sieve of Eratosthenes | O(n log log n) | O(n) | All primes up to n |
| Fast exponentiation | O(log exponent) | O(1) iterative | Modular power calculations |
Code Example
13.Space Complexity
Space complexity measures how memory grows with input size. It includes auxiliary data structures, recursion stack, memo tables, copied arrays, queues, heaps, and output storage when the output is part of the algorithm’s memory footprint. Many learners focus only on time and miss stack or table memory.
A familiar example is storing all monthly UPI transactions in a list before processing, which costs O(n) space. Streaming one transaction at a time and maintaining only a running total costs O(1) auxiliary space. In healthcare image processing, copying every image during transformation may double memory use, while in-place updates reduce auxiliary space when safe.
Recursive DFS uses O(h) stack space on a tree of height h, and O(V) in the worst case on a graph if recursion follows a long path. Merge sort uses O(n) auxiliary space because merging requires extra arrays. Heap sort is O(1) auxiliary space when performed in place.
Code Example
Algorithm Cheat Sheets
The tables below collect the standard complexities most often used in exams, code reviews, and interviews. Treat them as a revision sheet, but still derive the answer from loops, recursion, states, or graph representation when asked to explain.
Arrays And Strings
| Operation or Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| Array index access | O(1) | O(1) |
| Array search unsorted | O(n) | O(1) |
| Insert at end dynamic array | O(1) amortised | O(1) extra, O(n) during resize |
| Insert or delete at middle | O(n) | O(1) |
| Two-pointer scan | O(n) | O(1) |
| Sliding window | O(n) | O(1) to O(k) |
| Prefix sum build | O(n) | O(n) |
| Prefix sum range query | O(1) | O(n) preprocessing |
Linked Lists
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
| Access by index | O(n) | O(n) |
| Search | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| Insert after known node | O(1) | O(1) |
| Delete known node | O(n) if previous node unknown | O(1) |
| Reverse list | O(n) | O(n) |
Stacks And Queues
| Structure | Core Operations | Time Complexity | Space Complexity |
|---|---|---|---|
| Stack | push, pop, peek | O(1) | O(n) |
| Queue | enqueue, dequeue, front | O(1) | O(n) |
| Deque | insert and delete at both ends | O(1) | O(n) |
| Monotonic stack | next greater or smaller element | O(n) total | O(n) |
| Monotonic queue | sliding window maximum | O(n) total | O(k) |
Hashing And Sets
| Operation | Average Expected | Worst Case | Space |
|---|---|---|---|
| Insert key | O(1) | O(n) | O(n) |
| Search key | O(1) | O(n) | O(n) |
| Delete key | O(1) | O(n) | O(n) |
| Rehash resize | O(n) for that resize | O(n) | O(n) |
Graphs Summary
| Representation | Space | Check Edge | Iterate Neighbours |
|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) unless hashed | O(degree) |
| Adjacency matrix | O(V²) | O(1) | O(V) |
| Edge list | O(E) | O(E) | O(E) |
Learning Path
Use this path to move from recognising Big-O labels to deriving them under interview pressure. The goal is not memorising every row; it is knowing which operation causes the growth.
Frequently Asked Questions
What is a big o notation cheat sheet?
A big o notation cheat sheet is a quick reference that lists common algorithm and data structure complexities. It helps you compare approaches by growth rate, such as O(n), O(n log n), O(n²), and O(2ⁿ), rather than by machine-specific runtime.
What is the difference between time complexity and space complexity?
Time complexity measures how the number of operations grows with input size. Space complexity measures how memory usage grows, including auxiliary structures and recursion stack. A solution can have good time complexity but poor space complexity, such as DP with a large table.
What is the difference between Big-O, Omega, and Theta?
Big-O is an upper bound, Omega is a lower bound, and Theta is a tight bound. If merge sort is described as Theta(n log n), it means its growth is bounded above and below by n log n up to constant factors.
How do I calculate Big-O from code?
Count how many times the main work runs as input grows. Sequential loops add, nested loops multiply, halving loops are logarithmic, and recursive code is analysed through a recurrence or recursion tree. Drop constants and lower-order terms at the end.
When should I use O(n log n) sorting instead of O(n²) sorting?
Use O(n log n) sorting for medium or large inputs, production systems, and most interview solutions. O(n²) sorting may be acceptable for tiny arrays, nearly sorted data with insertion sort, or teaching purposes, but it scales poorly.
Why is binary search O(log n)?
Binary search halves the remaining search space after every comparison. After k steps, the remaining size is roughly n divided by 2ᵏ, so the search finishes when k is about log₂ n.
Is hash table lookup always O(1)?
No. Hash table lookup is expected O(1) when hashing distributes keys well and the table maintains a healthy load factor. In the worst case, many keys can collide and lookup can degrade to O(n).
What is amortised time complexity?
Amortised complexity describes the average cost per operation over a sequence, even if one operation is occasionally expensive. Dynamic array append is O(1) amortised because rare O(n) resizes are spread across many cheap appends.
What is the most common mistake in Big-O analysis?
The most common mistake is giving a complexity without assumptions. For example, BFS is O(V + E) only when using an adjacency list; representation matters. Another common error is ignoring recursion stack space.
Key Takeaways
The most important points are concrete: Big-O is an asymptotic growth bound, Theta is the tight bound, nested loops multiply, recursive calls add stack space, and graph complexity must mention V, E, and representation. Sorting, hashing, DP, and graph traversal are the highest-value areas to revise.
For GATE and interviews, expect questions on binary search O(log n), comparison sorting Omega(n log n), BFS and DFS O(V + E), hash table expected O(1) versus worst O(n), merge sort O(n log n) time and O(n) space, and DP complexity as states multiplied by transition cost.
The natural next step is to solve mixed algorithm problems and write the time and space complexity beside every solution before coding. Build your own one-page revision sheet from the tables above and update it whenever you learn a new pattern.