Complexity analysis is used to measure how much time and memory an algorithm requires as the size of its input increases. It helps us compare algorithms and understand their efficiency.
Complexity analysis is used to measure how much time and memory an algorithm requires as the size of its input increases. It helps us compare algorithms and understand their efficiency.
Complexity tells us how an algorithm's work and memory requirement grow when the amount of data becomes larger.
| Type | Measures |
|---|---|
| Time Complexity | How the number of operations grows with input size. |
| Space Complexity | How the memory requirement grows with input size. |
Time complexity describes how the number of operations performed by an algorithm grows as the input size n increases.
Time complexity usually talks about the number of steps or operations, not the actual time in seconds.
Space complexity describes how much memory an algorithm requires as the input size increases. It includes the memory needed for the input and the extra memory used by the algorithm.
If an algorithm uses only a fixed number of extra variables, its extra space remains constant even when n becomes larger.
Asymptotic analysis studies the growth of an algorithm for very large input sizes. It focuses on the growth rate and normally ignores constants and lower-order terms.
3n and 5n both have linear growth, so both are represented as O(n).
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort |
| O(nĀ²) | Quadratic | Bubble sort |
| O(2āæ) | Exponential | Some subset-generation problems |
Big-O notation represents an asymptotic upper bound on an algorithm's growth. It is commonly used to describe worst-case time complexity.
Big-O tells us how much an algorithm can grow at most, especially in the worst case.
Omega notation represents an asymptotic lower bound. It describes the minimum amount of growth or work required by an algorithm.
Omega tells us the minimum growth of an algorithm. It is commonly associated with the best-case situation.
In a linear search, if the required element is found at the first position, only one comparison may be required.
Theta notation represents a tight asymptotic bound. It is used when the upper and lower bounds have the same growth rate.
Theta tells us the exact growth order of an algorithm within constant factors when the upper and lower bounds match.
| Notation | Meaning | Simple Idea |
|---|---|---|
| O(g(n)) | Upper bound | Maximum / worst-case growth |
| Ī©(g(n)) | Lower bound | Minimum / best-case growth |
| Ī(g(n)) | Tight bound | Matching upper and lower growth |
In general, a slower-growing complexity is preferred when working with large input sizes.
O ā Upper Bound | Ī© ā Lower Bound | Ī ā Tight Bound
Suppose we search for a number in an unsorted array containing n elements.
| Case | Situation | Complexity |
|---|---|---|
| Best Case | Element is found at the first position. | Ī©(1) |
| Worst Case | Element is at the last position or absent. | O(n) |
| Concept | Remember |
|---|---|
| Time Complexity | Growth in number of operations. |
| Space Complexity | Growth in memory requirement. |
| Big-O | Upper bound / commonly used for worst case. |
| Big-Ī© | Lower bound / commonly associated with best case. |
| Big-Ī | Tight bound. |
Watch a beginner-friendly explanation of time complexity, space complexity and Big-O notation.
A short handwritten-style revision sheet for complexity notations will be provided here.
Use the mind map for quick revision of time complexity, space complexity and asymptotic notations.