Complexity Analysis
Complexity Analysis is the process of measuring how efficiently an algorithm performs as the input size increases.
In simple words:
Complexity analysis tells us how much time and memory an algorithm needs.
There are two main types:
- Time Complexity → How much time an algorithm takes
- Space Complexity → How much extra memory an algorithm uses
1. Why Do We Need Complexity Analysis?
Suppose we have two algorithms that solve the same problem.
Algorithm A
Takes:
1 second
Algorithm B
Takes:
100 seconds
Both produce the correct answer, but Algorithm A is more efficient.
The problem becomes more interesting when the input gets bigger.
Suppose we have n items.
| Input | Algorithm A | Algorithm B |
|---|---|---|
| 10 | 1 sec | 2 sec |
| 1,000 | 1 sec | 20 sec |
| 1,000,000 | 1 sec | 20,000 sec |
So we don't just want to know:
"How fast is it on my computer?"
We want to know:
"How does its performance grow when the input grows?"
That's what complexity analysis helps us understand.
2. What is Input Size?
We usually represent input size using n.
For example, suppose we have an array:
int arr[] = {10, 20, 30, 40, 50};
There are 5 elements.
So:
n = 5
If there are 1,000 elements:
n = 1000
If there are 1,000,000 elements:
n = 1,000,000
n simply represents the size of the input.
3. Time Complexity
Time complexity describes how the number of operations performed by an algorithm grows with input size.
For example:
int x = 10; int y = 20; int z = x + y;
These operations don't depend on n.
Whether your program has 10 items or 10 million items, these particular statements execute a fixed number of times.
So we consider this:
O(1)
4. Big O Notation
The most commonly used notation for complexity is Big O notation.
Examples:
O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ) O(n!)
Big O describes the growth rate of an algorithm.
You don't normally use Big O to say:
"This program takes exactly 2.35 seconds."
Instead, you say:
"This algorithm is O(n)."
5. O(1) — Constant Time
O(1) means the amount of work doesn't depend on the size of the input.
Example:
int arr[] = {10, 20, 30, 40, 50}; cout << arr[2];
We directly access index 2.
Whether the array contains:
5 elements
or:
5,000,000 elements
we can directly access arr[2].
Therefore:
Time Complexity = O(1)
Another example
int x = 10; x++;
Constant number of operations:
O(1)
6. O(n) — Linear Time
Now consider:
for(int i = 0; i < n; i++) { cout << arr[i]; }
If:
n = 5
the loop runs 5 times.
If:
n = 100
it runs 100 times.
If:
n = 1,000,000
it runs 1,000,000 times.
Therefore:
Time Complexity = O(n)
This is called linear time.
Example
Input size Operations 10 10 100 100 1,000 1,000 10,000 10,000
The operations grow directly with n.
7. O(n²) — Quadratic Time
Consider nested loops:
for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << i << " " << j; } }
The outer loop runs:
n times
For every outer iteration, the inner loop also runs:
n times
Therefore:
n × n = n²
So:
Time Complexity = O(n²)
Example
If:
n = 10
operations ≈
10 × 10 = 100
If:
n = 100
operations ≈
100 × 100 = 10,000
If:
n = 1,000
operations ≈
1,000 × 1,000 = 1,000,000
This is why quadratic algorithms can become slow very quickly.
8. O(log n) — Logarithmic Time
O(log n) is very efficient.
A classic example is Binary Search.
Suppose you have:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
You want to find 13.
Instead of checking every number, binary search repeatedly cuts the search space roughly in half.
16 elements ↓ 8 elements ↓ 4 elements ↓ 2 elements ↓ 1 element
That's approximately:
log₂(n)
So:
Binary Search = O(log n)
This is much faster than O(n) for very large inputs.
9. O(n log n)
This complexity commonly appears in efficient sorting algorithms such as:
- Merge Sort
- Heap Sort
- Average-case Quick Sort
For example:
n × log n
Therefore:
O(n log n)
It is generally more efficient than:
O(n²)
for large n.
10. O(2ⁿ) — Exponential Time
An algorithm with:
O(2ⁿ)
can become extremely expensive as n increases.
For example:
n = 1 → 2 n = 2 → 4 n = 3 → 8 n = 10 → 1,024 n = 20 → 1,048,576 n = 30 → 1,073,741,824
Exponential growth is very fast.
Some recursive solutions to problems can have exponential complexity if they repeatedly explore two or more possibilities.
11. O(n!)
O(n!) is even faster-growing.
Factorial means:
n! = n × (n-1) × (n-2) × ... × 1
For example:
5! = 120 10! = 3,628,800
Factorial complexity often appears in brute-force solutions involving permutations.
For example:
Try every possible ordering of
nobjects.
There are:
n!
possible arrangements.
12. Complexity Growth Comparison
From generally more efficient to less efficient:
O(1) ↓ O(log n) ↓ O(n) ↓ O(n log n) ↓ O(n²) ↓ O(2ⁿ) ↓ O(n!)
For large input sizes, the difference can be enormous.
13. How to Calculate Time Complexity
Let's learn the basic rules.
Rule 1: Ignore Constants
Consider:
for(int i = 0; i < n; i++) { cout << i; }
Runs:
n times
Therefore:
O(n)
Now:
for(int i = 0; i < n; i++) { cout << i; } for(int i = 0; i < n; i++) { cout << i; }
Total:
n + n = 2n
Big O ignores the constant 2.
Therefore:
O(2n) → O(n)
14. Rule 2: Drop Smaller Terms
Suppose:
O(n² + n)
For very large n, n² grows much faster than n.
Therefore:
O(n² + n) → O(n²)
Similarly:
O(n³ + n² + n) → O(n³)
And:
O(n + 100) → O(n)
15. Sequential Operations
Consider:
for(int i = 0; i < n; i++) { cout << i; } for(int i = 0; i < n; i++) { cout << i; }
First loop:
O(n)
Second loop:
O(n)
Together:
O(n + n)
Therefore:
O(2n)
Drop the constant:
O(n)
16. Nested Loops
Consider:
for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << i << j; } }
Outer:
n
Inner:
n
Because the inner loop runs for every outer iteration:
n × n
Therefore:
O(n²)
Important rule
Sequential loops → Add Nested loops → Multiply
17. Different-Sized Nested Loops
Consider:
for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cout << i << j; } }
Outer loop:
n
Inner loop:
m
Therefore:
O(n × m)
or:
O(nm)
Don't automatically write O(n²) unless both loops depend on the same input size.
18. Logarithmic Example
Consider:
int i = 1; while(i < n) { i = i * 2; }
Values of i:
1 2 4 8 16 32 64 ...
The value doubles every iteration.
The number of iterations is approximately:
log₂(n)
Therefore:
O(log n)
19. Space Complexity
Time isn't the only thing we care about.
We also need to consider memory.
That's called space complexity.
Example:
int x;
Only a constant amount of additional memory is required.
Therefore:
Space Complexity = O(1)
20. O(n) Space
Consider:
int arr[n];
If n increases, the amount of memory required also increases.
Therefore:
Space Complexity = O(n)
Example:
n = 10 → memory for 10 elements n = 100 → memory for 100 elements n = 1000 → memory for 1000 elements
21. Time vs Space Complexity
These are different.
Consider:
int sum = 0; for(int i = 0; i < n; i++) { sum += arr[i]; }
The loop runs n times:
Time = O(n)
But we only use a few extra variables:
sum i
So:
Extra Space = O(1)
Therefore:
Time Complexity → O(n) Space Complexity → O(1)
22. Best, Average and Worst Case
An algorithm can behave differently depending on the input.
Suppose we search for a number:
[10, 20, 30, 40, 50]
We want to find 10.
It's the first element.
Best Case
Found immediately:
O(1)
If we search for 50, we may need to check everything:
10 → 20 → 30 → 40 → 50
Worst Case
O(n)
The average case describes typical expected behavior over inputs, depending on the assumptions about those inputs.
23. Important: Big O Is Not Exact Running Time
Suppose two algorithms are:
Algorithm A → O(n) Algorithm B → O(n)
That doesn't necessarily mean they take exactly the same amount of time.
For example:
A → 2n operations B → 100n operations
Both are:
O(n)
Big O focuses on the growth rate, not exact execution time.
24. Why Constants Are Ignored
Suppose:
A = 10n B = 100n
For small inputs, the difference matters.
But complexity analysis focuses on what happens as n becomes very large.
Both grow linearly:
10n 100n
So both belong to:
O(n)
25. Common Complexity Examples
| Code / Algorithm | Time Complexity |
|---|---|
| Access array element | O(1) |
| Single loop | O(n) |
| Two separate loops | O(n) |
| Nested loops | O(n²) |
| Binary search | O(log n) |
| Efficient sorting | O(n log n) |
| Some brute-force recursive algorithms | O(2ⁿ) |
| Generate all permutations | O(n!) |
These are patterns you should learn to recognize.
26. A Very Important Example
Consider:
for(int i = 0; i < n; i++) { cout << i; } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << i << j; } }
First part:
O(n)
Second part:
O(n²)
Total:
O(n + n²)
Drop the smaller term:
O(n²)
Therefore:
Time Complexity = O(n²)
27. Complexity Analysis Cheat Sheet
Remember these patterns:
Constant O(1) ↓ Doesn't depend on n Logarithmic O(log n) ↓ Input repeatedly divided Linear O(n) ↓ One pass through input Linearithmic O(n log n) ↓ Efficient sorting Quadratic O(n²) ↓ Two nested loops Exponential O(2ⁿ) ↓ Repeatedly exploring combinations Factorial O(n!) ↓ All permutations
28. The Main Rules to Remember
Rule 1
Single loop
for(...)
Usually:
O(n)
Rule 2
Nested loops
for(...) for(...)
Usually:
O(n²)
Rule 3
Separate loops
for(...) for(...)
Add them:
O(n + n) → O(n)
Rule 4
Nested different variables
O(n × m)
Rule 5
Repeatedly divide/multiply by a constant
O(log n)
Rule 6
Ignore constants
O(5n) → O(n)
Rule 7
Keep the fastest-growing term
O(n² + n) → O(n²)
29. Why Complexity Analysis Comes Before Arrays
Your DSA roadmap starts:
Introduction ↓ Complexity Analysis ↓ Arrays
This order is important.
When we study arrays, we'll not only learn:
"How does an array work?"
We'll also ask:
"How fast is accessing an element?"
"How fast is searching?"
"How fast is insertion?"
"How much memory does it use?"
For example, accessing:
arr[5]
is generally:
O(1)
But searching for an arbitrary value in an unsorted array can require:
O(n)
So complexity analysis gives us the language to evaluate the data structures and algorithms we study later.
Final Concept
The easiest way to remember this entire topic is:
Complexity Analysis │ ┌─────────┴─────────┐ ↓ ↓ Time Complexity Space Complexity │ │ How much work? How much memory? │ ┌─────┼─────┬─────┐ ↓ ↓ ↓ ↓ O(1) O(log n) O(n) O(n²)
And the central question is always:
"When my input becomes bigger, how does my algorithm's resource usage grow?"