Complexity Analysis is used to measure the efficiency of an algorithm in terms of time and space resources.
| Notation | Name | Meaning |
|---|---|---|
| O(1) | Constant | Execution time independent of input size |
| O(log n) | Logarithmic | Increases slowly with input size |
| O(n) | Linear | Proportional to input size |
| O(n log n) | Linearithmic | Common in efficient sorting |
| O(n²) | Quadratic | Nested loops over input |
| O(2ⁿ) | Exponential | Doubles with each increase in input |
| O(n!) | Factorial | All permutations considered |
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| Linear Search | O(n) | O(1) |
| Binary Search | O(log n) | O(1) |
| Bubble Sort | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(log n) |
| DFS / BFS | O(V + E) | O(V) |
Analyzing complexity helps developers compare algorithms and choose the most efficient one for a given task. It’s a crucial skill in algorithm design and optimization.
Take quizzes related to this topic and see where you stand!
Start Quiz Now