An algorithm is a step-by-step set of instructions designed to solve a specific problem or complete a task. There are multiple ways or multiples set of instructions to solve any problem or task. We may use different method to get the same solution, say different paths to reach same destination.
Imagine you're a programmer faced with solving a problem. There are often many ways to approach it, each with its own method or algorithm. But how do you know which solution is best? This is where evaluating algorithms comes into play.
Performance and efficiency are key factors when choosing an algorithm. Performance refers to how quickly your algorithm runs—its execution time. Efficiency, on the other hand, involves how much memory or resources your algorithm consumes. Both aspects are crucial because they affect how well your application runs in the real world.
For programmers, understanding these factors isn’t just about making software work; it’s about making it work well. This is where Big O, which we also call as Big O notation come to picture.
Understanding algorithm efficiency is essential for writing software that remains fast, reliable, and scalable. Big O notation provides a standard way to describe how an algorithm’s performance changes as the size of its input increases.
We have explained Big O Notations with Practice Problems in our previous post, here were are going to go for Big O cheat sheet which explains the most common time and space complexities, shows practical examples, and provides guidance for choosing efficient algorithms and data structures.
How does the amount of work or memory required by an algorithm change as the input size increases?
The input size is commonly represented by 𝑛 n. Big O focuses on the dominant factor and ignores constants and lower-order terms.
- Time complexity: How long an algorithm takes to run.
- Space complexity: How much additional memory an algorithm requires.
- Scalability: How performance changes with larger inputs.
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Scanning an array |
| O(n log n) | Linearithmic | Efficient comparison-based sorting |
| O(n2) | Quadratic | Comparing every pair of elements |
| O(n3) | Cubic | Some matrix algorithms |
| O(2n) | Exponential | Brute-force subset generation |
| O(n!) | Factorial | Brute-force permutation generation |
Big O for Common Data Structures
The following table shows typical time complexities for frequently used data structures. Values can vary depending on the implementation and operation.
| Data structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Dynamic array | O(1) | O(n) | O(1) amortized at end | O(n) |
| Linked list | O(n) | O(n) | O(1) with a known node | O(1) with a known node |
| Hash table | Not typically indexed | O(1) average | O(1) average | O(1) average |
| Binary search tree | O(log n) average | O(log n) average | O(log n) average | O(logn)O average |
| Balanced search tree | O(log n) | O(log n) | O(log n) | O(log n) |
| Heap | Not generally supported | O(n) | O(log n) | O(log n) |
Big O Quick Reference
| Complexity | Practical interpretation |
|---|---|
| O(1) | Excellent; unaffected by input size |
| O(log n) | Very efficient; scales well |
| O(n) | Efficient for most ordinary workloads |
| O(n log n) | Efficient for large-scale sorting and processing |
| O(n 2) | Often acceptable for small inputs |
| O(n3) | Usually limited to small datasets |
| O(2n) | Becomes impractical quickly |
| O(n!) | Practical only for very small inputs |
The Big O Hierarchy (Best to Worst)
| Complexity | Name | Practical Metaphor | Common Culprit / Example |
|---|---|---|---|
| O(1) | Constant | Grabbing a specific TV remote | Hash map lookup, array index access |
| O(log n) | Logarithmic | Binary search in a phone book | Halving search space (balanced BSTs) |
| O(n) | Linear | Scanning a single-file line of people | Single loop over an unsorted array |
| O(n log n) | Linearithmic | Sorting a deck via merge-sort/quicksort | Efficient comparison-based sorts |
| O(n 2) | Quadratic | Comparing every photo with every other photo | Nested loops over the same dataset |
| O(2n) | Exponential | Branching puzzle decisions (include/exclude) | Naive recursive Fibonacci, subset generation |
| O(n!) | Factorial | Generating all travel route permutations | Traveling Salesperson brute force |
