Complexity analysis is the study of the resources required by an algorithm to solve a problem as the input size increases.
The two major resources are:
- Time Complexity
- Space Complexity
Time complexity describes how the number of computational operations performed by an algorithm grows as a function of the input size n.
It does not measure the exact execution time in seconds. Instead, it describes how the computational work grows as the input size increases.
Space complexity describes how the memory requirements of an algorithm grow as a function of the input size n.
It includes memory used for variables, data structures, and other operations. Depending on the convention, we may analyze total space or auxiliary space.
- Total space: All memory used by the algorithm, including the input.
- Auxiliary space: Extra memory used by the algorithm, excluding the input storage.
Asymptotic notations are mathematical notations used to describe the growth rate of an algorithm as the input size n becomes very large.
There are three major asymptotic notations:
- Big-Omega
Ω - Big-Theta
Θ - Big-O
O
Big-O describes an asymptotic upper bound on the growth of an algorithm's resource usage.
It is commonly used when discussing worst-case time complexity.
Big-Omega describes an asymptotic lower bound on the growth of an algorithm's resource usage.
It is commonly used when discussing best-case time complexity.
Big-Theta describes a tight asymptotic bound on the growth of an algorithm's resource usage.
It means the growth is bounded both above and below by the same asymptotic order.
| Notation | Meaning | Common Association |
|---|---|---|
O(g(n)) |
Upper bound | Worst-case analysis |
Ω(g(n)) |
Lower bound | Best-case analysis |
Θ(g(n)) |
Tight bound | Exact asymptotic growth order |
Important: These notations describe mathematical bounds. Big-O does not inherently mean worst case, Big-Omega does not inherently mean best case, and Big-Theta does not inherently mean average case. The actual case depends on the algorithm and the analysis being performed.
for i in range(1, 101):
print("hii")The loop always executes 100 times, regardless of the input size.
There is no input variable n controlling the number of iterations.
Therefore:
Time Complexity: O(1)
This is called constant time complexity because the amount of computational work does not grow with the input size.
for i in range(1, n + 1):
print("hii")The loop executes n times.
If n = 5, the loop executes 5 times.
If n = 100, the loop executes 100 times.
Therefore:
Time Complexity: O(n)
This is called linear time complexity.
for i in range(1, n + 1):
for j in range(1, n + 1):
print("hii")The outer loop executes n times.
For every iteration of the outer loop, the inner loop executes n times.
Total operations:
n × n = n²
Therefore:
Time Complexity: O(n²)
This is called quadratic time complexity.
Consider the following code:
for i in range(1, n + 1):
if i**2 <= n:
print("hii")
else:
print("bye")
breakThe condition is:
i² <= n
Taking the square root:
i <= √n
The loop continues until i exceeds √n. After that, the break statement terminates the loop.
The number of iterations is proportional to √n.
Therefore:
Time Complexity: O(√n)
Correction: Your original example used range(100), which has a fixed limit. That exact code has O(1) time complexity, not O(√n). The version above uses range(1, n + 1) to demonstrate square root complexity.
for i in range(1, n + 1):
for j in range(1, n + 1):
if j <= i:
for k in range(101):
print("hii")
breakThe outer loop executes n times.
For every outer-loop iteration, j starts at 1.
Since i >= 1, the condition j <= i is true on the first iteration of the inner loop.
The k loop therefore executes 101 times, and then break terminates the j loop.
Consequently, each outer-loop iteration performs a constant amount of work.
Total work:
101 × n
Ignoring constant factors:
Time Complexity: O(n)
Important: The break statement changes the complexity here. The inner j loop does not execute n times because it terminates during its first iteration.
i = 1
while i <= n:
print("hii")
i += 1
j = 1
while j <= n:
print("bye")
j += 1First loop:
O(n)
Second loop:
O(n)
Total complexity:
O(n) + O(n)
= O(2n)
= O(n)
Therefore:
Time Complexity: O(n)
Rule: When adding the complexities of sequential operations, discard constant factors and retain the dominant growth rate.
i = 1
while i < n:
print("hii")
i *= 2The value of i doubles during every iteration.
For example, when n = 16:
i = 1
i = 2
i = 4
i = 8
The next value would be 16, at which point the condition i < n becomes false.
The values follow this pattern:
2⁰, 2¹, 2², 2³, ..., 2ᵏ
After k iterations, the value is proportional to 2ᵏ.
When it reaches n:
2ᵏ = n
Taking the logarithm:
k = log₂(n)
Therefore:
Time Complexity: O(log n)
This is called logarithmic time complexity.
The base of the logarithm is omitted in Big-O notation because changing the base only introduces a constant factor.
Consider the following pseudocode:
for i = 1 to n:
for j = 1 to i²:
for k = 1 to j/2:
print("xcvbn")
The outer loop executes n times.
For a fixed value of i, the j loop executes up to i² times.
For each j, the k loop executes approximately j/2 times.
Since constant factors are ignored, the number of operations for a fixed i is proportional to:
1 + 2 + 3 + ... + i²
Using the summation formula:
1 + 2 + 3 + ... + m = m(m + 1)/2
Substitute m = i²:
i²(i² + 1)/2
The dominant term is proportional to:
i⁴
Now sum across all values of i:
1⁴ + 2⁴ + 3⁴ + ... + n⁴
The sum of fourth powers grows proportionally to n⁵.
Therefore:
Time Complexity: O(n⁵)
Correction: The original O(n⁴) answer does not account for all three loop bounds. Because j runs up to i² and k runs proportionally to j, the correct result is O(n⁵).
for i = 1 to n:
print("hi")
for i = 1 to n²:
print("hi")
for i = 1 to n³:
print("hi")
First loop:
O(n)
Second loop:
O(n²)
Third loop:
O(n³)
Total complexity:
O(n) + O(n²) + O(n³)
The dominant term is n³.
Therefore:
Time Complexity: O(n³)
This is called cubic time complexity.
Rule: When adding different growth rates, keep the dominant term.
for i = 1 to n:
for j = 1 to n, increment j by i:
print("hii")
For each value of i, the inner loop increases j by i.
Therefore, the inner loop executes approximately:
n/i
times.
Across all outer-loop iterations, the total number of operations is proportional to:
n/1 + n/2 + n/3 + ... + n/n
Factor out n:
n(1 + 1/2 + 1/3 + ... + 1/n)
The harmonic sum grows proportionally to log n.
Therefore:
Time Complexity: O(n log n)
This is called linearithmic time complexity.
def create_list(n):
numbers = []
for i in range(n):
numbers.append(i)
return numbersThe loop executes n times.
Appending to a Python list takes amortized constant time.
Therefore:
Time Complexity: O(n)
The list stores n elements.
Therefore:
Space Complexity: O(n)
def create_nested_list(n):
numbers = []
for i in range(n):
row = []
for j in range(n):
row.append(j)
numbers.append(row)
return numbersThe outer loop executes n times.
For each outer-loop iteration, the inner loop executes n times.
Total operations:
n × n = n²
Therefore:
Time Complexity: O(n²)
There are n rows, and each row contains n elements.
Total elements:
n × n = n²
Therefore:
Space Complexity: O(n²)
Important: Creating a nested list does not automatically mean O(n²). The complexity depends on how many elements are created. A list containing n empty lists requires only O(n) space, while an n × n list requires O(n²) space.
The following list is ordered approximately from slower-growing to faster-growing complexity.
| Complexity | Name | Example |
|---|---|---|
O(1) |
Constant | Accessing an element by index |
O(log n) |
Logarithmic | Binary Search |
O(√n) |
Square root | Checking divisors up to √n |
O(n) |
Linear | Traversing an array |
O(n log n) |
Linearithmic | Merge Sort |
O(n²) |
Quadratic | Two full nested loops |
O(n³) |
Cubic | Three full nested loops |
O(2ⁿ) |
Exponential | A typical exhaustive subset search |
O(n!) |
Factorial | Generating all permutations |
O(nⁿ) |
Exponential | Enumerating all length-n sequences with n choices per position |
These are common growth classes. The exact complexity of an algorithm depends on its implementation and the operations it performs.
| Concept | Meaning |
|---|---|
| Time Complexity | Growth in computational work |
| Space Complexity | Growth in memory requirements |
| Auxiliary Space | Extra memory used, excluding input storage |
| Notation | Meaning |
|---|---|
O(g(n)) |
Asymptotic upper bound |
Ω(g(n)) |
Asymptotic lower bound |
Θ(g(n)) |
Asymptotically tight bound |
O(1) → Constant
O(log n) → Logarithmic
O(√n) → Square root
O(n) → Linear
O(n log n) → Linearithmic
O(n²) → Quadratic
O(n³) → Cubic
O(2ⁿ) → Exponential
O(n!) → Factorial
O(nⁿ) → Exponential
- Constant loop bounds: A fixed number of iterations gives
O(1)time. - Single input-dependent loop: Usually
O(n). - Two full nested loops: Usually
O(n²). - Three full nested loops: Usually
O(n³). - Doubling or halving the problem size: Often
O(log n). - Sequential loops: Add their complexities, then retain the dominant term.
- Nested loops: Analyze how many times the innermost operation executes.
- Break statements: Check when the loop actually terminates; a
breakcan change the complexity. - Ignore constant factors:
O(2n)simplifies toO(n). - Retain the dominant term:
O(n² + n + 1)simplifies toO(n²). - Memory usage: An
n × ncollection of stored elements requiresO(n²)space. - Analyze the actual code: Similar-looking loops can have different complexities because their bounds, increments, and termination conditions differ.