Time Complexity.
Time complexity is a fundamental concept in computer science that helps us understand how an algorithm's performance scales with input size. It's expressed using Big O notation, which describes the upper bound of an algorithm's growth rate.
Understanding these complexity classes allows developers to make informed decisions about which algorithms to use for different scenarios, optimizing for speed or memory usage depending on requirements.
Time Complexity
Measures how the running time of an algorithm increases with the size of the input. This helps us predict how scalable our solution is for large datasets.
Space Complexity
Measures how much memory an algorithm needs relative to the input size. Critical for applications with memory constraints or dealing with very large datasets.
Time Complexity Growth Comparison
Understanding Complexity Classes
Understanding time complexity helps you choose the right algorithm for your specific needs. Here's a breakdown of common complexity classes and what they mean for your code's performance:
O(1) - Constant Time
Operations that take the same amount of time regardless of input size.
COMMON EXAMPLES:
- Array access with index
- Push/pop operations on a stack
- Inserting at the beginning of a linked list
O(log n) - Logarithmic Time
Runtime grows logarithmically with input size. Common in algorithms that divide the problem in half each time.
COMMON EXAMPLES:
- Binary search
- Finding an element in a balanced search tree
- Certain divide and conquer algorithms
O(n) - Linear Time
Runtime grows linearly with input size. Operations performed once for each input element.
COMMON EXAMPLES:
- Linear search
- Traversing an array or linked list
- Finding the maximum/minimum value in an unsorted array
O(n log n) - Linearithmic Time
Common in efficient sorting algorithms and operations that combine linear and logarithmic complexities.
COMMON EXAMPLES:
- Merge sort
- Heap sort
- Quick sort (average case)
O(n²) - Quadratic Time
Runtime grows with the square of input size. Often involves nested iterations over the data.
COMMON EXAMPLES:
- Bubble sort
- Selection sort
- Simple matrix multiplication
- Checking all possible pairs in an array
O(n!) - Factorial Time
Runtime grows with the factorial of input size. These algorithms become impractical very quickly.
COMMON EXAMPLES:
- Brute force traveling salesman problem
- Generating all permutations
- Solving the n-queens problem with brute force
Algorithm Complexities
| Algorithm | Category | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|---|
| Bubble Sort | Sorting | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | Sorting | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | Sorting | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | Sorting | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | Sorting | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | Sorting | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting Sort | Sorting | O(n+k) | O(n+k) | O(n+k) | O(n+k) |
| Radix Sort | Sorting | O(nk) | O(nk) | O(nk) | O(n+k) |
| Linear Search | Searching | O(1) | O(n) | O(n) | O(1) |
| Binary Search | Searching | O(1) | O(log n) | O(log n) | O(1) |
| Jump Search | Searching | O(1) | O(√n) | O(√n) | O(1) |
| Interpolation Search | Searching | O(1) | O(log log n) | O(n) | O(1) |
| Breadth-First Search | Graph | O(V+E) | O(V+E) | O(V+E) | O(V) |
| Depth-First Search | Graph | O(V+E) | O(V+E) | O(V+E) | O(V) |
| Dijkstra's Algorithm | Graph | O((V+E)log V) | O((V+E)log V) | O((V+E)log V) | O(V) |
| Bellman-Ford | Graph | O(VE) | O(VE) | O(VE) | O(V) |
| Floyd-Warshall | Graph | O(V³) | O(V³) | O(V³) | O(V²) |
| Prim's Algorithm | Graph | O(E log V) | O(E log V) | O(E log V) | O(V+E) |
| Kruskal's Algorithm | Graph | O(E log E) | O(E log E) | O(E log E) | O(V+E) |
| Array Access | Data Structure | O(1) | O(1) | O(1) | O(1) |
| Array Search | Data Structure | O(1) | O(n) | O(n) | O(1) |
| Array Insertion | Data Structure | O(1) | O(n) | O(n) | O(1) |
| Hash Table Search | Data Structure | O(1) | O(1) | O(n) | O(n) |
| Binary Search Tree Search | Data Structure | O(1) | O(log n) | O(n) | O(n) |
| AVL Tree Operations | Data Structure | O(log n) | O(log n) | O(log n) | O(n) |