Time and Space Complexity
⏱ Estimated reading time: 1 min
Time and Space Complexity
Time and space complexity measure how efficiently an algorithm uses computational resources such as time and memory. Understanding complexity helps you compare and choose better algorithms.
Time Complexity
Time complexity measures how the running time of an algorithm increases as the input size increases. It is expressed using Big O Notation.
Common Time Complexities:
- O(1) – Constant time
- O(log n) – Logarithmic time
- O(n) – Linear time
- O(n log n) – Log-linear time
- O(n²) – Quadratic time
- O(2ⁿ) – Exponential time
Example:
If an algorithm loops through an array of size n once, its time complexity is O(n).
Space Complexity
Space complexity measures how much extra memory an algorithm requires to execute. It includes:
- Input Space
- Auxiliary Space (temporary variables, recursion stack, etc.)
Big O Notation
Big O describes the upper bound of an algorithm’s growth rate. It helps estimate the worst-case performance.
| Algorithm | Best Case | Worst Case |
|---|---|---|
| Linear Search | O(1) | O(n) |
| Binary Search | O(1) | O(log n) |
| Bubble Sort | O(n) | O(n²) |
| Merge Sort | O(n log n) | O(n log n) |
Conclusion
Analyzing time and space complexity is critical for building scalable and efficient software. Always aim for the best possible performance within acceptable resource limits.
Register Now
Share this Post
← Back to Tutorials