Complexity Analysis Summary
📘 Data Structure and Algorithm
👁 86 views
📅 Nov 05, 2025
⏱ Estimated reading time: 1 min
Complexity Analysis Summary
Complexity Analysis is used to measure the efficiency of an algorithm in terms of time and space resources.
Types of Complexity
- Time Complexity: How the running time grows with input size.
- Space Complexity: How much extra memory is required.
Common Asymptotic Notations
| 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 |
Best, Average, and Worst Case
- Best Case: Minimum possible time.
- Average Case: Expected time over all inputs.
- Worst Case: Maximum time taken for any input.
Example Comparisons
| 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) |
Conclusion
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.
🔒 Some advanced sections are available for Registered Members
Register Now
Register Now
Share this Post
← Back to Tutorials