Complexity Analysis
Complexity Analysis¶
Overview¶
Learn how to measure algorithm efficiency. Understanding Big O notation and the ability to analyze time/space complexity of code is fundamental to algorithm learning.
Table of Contents¶
- Why Do We Need Complexity Analysis?
- Big O Notation
- Time Complexity
- Space Complexity
- Complexity Analysis Examples
- Practical Analysis Tips
- Practice Problems
1. Why Do We Need Complexity Analysis?¶
Execution Time Limitations¶
Actual execution time depends on:
- Hardware performance (CPU, memory)
- Programming language
- Compiler optimization
- Input data characteristics
Advantages of Complexity Analysis¶
1. Hardware independent
2. Understand growth rate with input size
3. Objective algorithm comparison
4. Predict scalability
Example: Same Problem, Different Algorithms¶
Problem: Find maximum value in n numbers
Method 1: Sequential search β O(n)
Method 2: Sort then get last element β O(n log n)
When n = 1,000,000:
- Method 1: ~1,000,000 comparisons
- Method 2: ~20,000,000 operations
β Method 1 is about 20Γ faster
2. Big O Notation¶
Definition¶
Big O: When input size n increases,
represents the upper bound of operation count
f(n) = O(g(n))
β f(n) does not grow faster than a constant multiple of g(n)
Notation Rules¶
1. Ignore constants
O(2n) = O(n)
O(100) = O(1)
2. Ignore lower-order terms
O(nΒ² + n) = O(nΒ²)
O(nΒ³ + nΒ² + n) = O(nΒ³)
3. Keep only highest-order term
O(3nΒ² + 2n + 1) = O(nΒ²)
Major Complexity Classes¶
βββββββββββββββ¬ββββββββββββββββ¬ββββββββββββββββββββββ
β Complexity β Name β Example β
βββββββββββββββΌββββββββββββββββΌββββββββββββββββββββββ€
β O(1) β Constant β Array index access β
β O(log n) β Logarithmic β Binary search β
β O(n) β Linear β Sequential search β
β O(n log n) β Linearithmic β Merge sort β
β O(nΒ²) β Quadratic β Bubble sort β
β O(nΒ³) β Cubic β Floyd-Warshall β
β O(2βΏ) β Exponential β Subset enumeration β
β O(n!) β Factorial β Permutation enum β
βββββββββββββββ΄ββββββββββββββββ΄ββββββββββββββββββββββ
Complexity Comparison Graph¶
Operations
β
β O(n!)
β β±
β O(2βΏ)
β β±
β O(nΒ²)
β β±
β O(n log n)
β β±
β O(n)
β β±
βββββββO(log n)
βββββββO(1)
βββββββββββββββββββββββββββββββββ n (input size)
Operation Counts by Input Size¶
ββββββββ¬ββββββββββ¬ββββββββββ¬βββββββββββ¬ββββββββββββ¬βββββββββββββ
β n β O(log n)β O(n) βO(n log n)β O(nΒ²) β O(2βΏ) β
ββββββββΌββββββββββΌββββββββββΌβββββββββββΌββββββββββββΌβββββββββββββ€
β 10 β 3 β 10 β 33 β 100 β 1,024 β
β 100 β 7 β 100 β 664 β 10,000 β 10Β³β° β
β 1000 β 10 β 1,000 β 9,966 β 1,000,000 β 10Β³β°β° β
β 10βΆ β 20 β 10βΆ β 2Γ10β· β 10ΒΉΒ² β β β
ββββββββ΄ββββββββββ΄ββββββββββ΄βββββββββββ΄ββββββββββββ΄βββββββββββββ
3. Time Complexity¶
3.1 O(1) - Constant Time¶
// C
int getFirst(int arr[], int n) {
return arr[0]; // always 1 operation
}
int getElement(int arr[], int index) {
return arr[index]; // independent of array size
}
// C++
int getFirst(const vector<int>& arr) {
return arr[0];
}
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
# Python
def get_first(arr):
return arr[0]
def get_element(arr, index):
return arr[index]
3.2 O(log n) - Logarithmic Time¶
// C - Binary search
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
// Search range halves each iteration
// n β n/2 β n/4 β ... β 1
// Iterations: logβ(n)
// C++
int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
# Python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
3.3 O(n) - Linear Time¶
// C - Find maximum
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) { // n-1 iterations
if (arr[i] > max)
max = arr[i];
}
return max;
}
// C++
int findMax(const vector<int>& arr) {
int maxVal = arr[0];
for (int i = 1; i < arr.size(); i++) {
maxVal = max(maxVal, arr[i]);
}
return maxVal;
}
// Using STL
int findMaxSTL(const vector<int>& arr) {
return *max_element(arr.begin(), arr.end());
}
# Python
def find_max(arr):
max_val = arr[0]
for x in arr[1:]:
if x > max_val:
max_val = x
return max_val
# Using built-in function
def find_max_builtin(arr):
return max(arr)
3.4 O(n log n) - Linearithmic Time¶
// C - Merge sort (concept)
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // T(n/2)
mergeSort(arr, mid + 1, right); // T(n/2)
merge(arr, left, mid, right); // O(n)
}
}
// T(n) = 2T(n/2) + O(n) = O(n log n)
// C++ - STL sort
#include <algorithm>
void sortArray(vector<int>& arr) {
sort(arr.begin(), arr.end()); // O(n log n)
}
# Python
def sort_array(arr):
return sorted(arr) # O(n log n) - Timsort
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort() # in-place sort
3.5 O(nΒ²) - Quadratic Time¶
// C - Bubble sort
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // n-1 times
for (int j = 0; j < n - i - 1; j++) { // n-i-1 times
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(nΒ²)
// C++ - Nested loops
void printPairs(const vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << arr[i] << ", " << arr[j] << endl;
}
}
}
// n Γ n = O(nΒ²)
# Python
def print_pairs(arr):
n = len(arr)
for i in range(n):
for j in range(n):
print(arr[i], arr[j])
3.6 O(2βΏ) - Exponential Time¶
// C - Fibonacci (recursive, inefficient)
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
// T(n) = T(n-1) + T(n-2) β O(2βΏ)
// C++ - Generate subsets
void generateSubsets(vector<int>& arr, int index, vector<int>& current) {
if (index == arr.size()) {
// Print current subset
for (int x : current) cout << x << " ";
cout << endl;
return;
}
// Exclude current element
generateSubsets(arr, index + 1, current);
// Include current element
current.push_back(arr[index]);
generateSubsets(arr, index + 1, current);
current.pop_back();
}
// Generates 2βΏ subsets
# Python - Generate subsets
def generate_subsets(arr):
result = []
n = len(arr)
for i in range(1 << n): # 2^n iterations
subset = []
for j in range(n):
if i & (1 << j):
subset.append(arr[j])
result.append(subset)
return result
4. Space Complexity¶
4.1 Concept¶
Space Complexity = Amount of memory used by algorithm
Components:
1. Input space: Storage for input data
2. Auxiliary space: Additional memory for algorithm execution
Generally only auxiliary space is counted
4.2 O(1) - Constant Space¶
// C - In-place swap
void reverseArray(int arr[], int n) {
int left = 0, right = n - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
// Only 3 variables used (left, right, temp)
# Python
def reverse_array(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
4.3 O(n) - Linear Space¶
// C - Array copy
int* copyArray(int arr[], int n) {
int* copy = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
copy[i] = arr[i];
}
return copy;
}
// Requires additional memory for n elements
// C++ - Merge process in merge sort
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right - left + 1); // O(n) additional space
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int i = 0; i < k; i++)
arr[left + i] = temp[i];
}
# Python
def copy_array(arr):
return arr[:] # O(n) space
4.4 O(log n) - Logarithmic Space (Recursion Stack)¶
// C - Binary search (recursive)
int binarySearchRecursive(int arr[], int left, int right, int target) {
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
return binarySearchRecursive(arr, mid + 1, right, target);
else
return binarySearchRecursive(arr, left, mid - 1, target);
}
// Recursion depth: O(log n) β Stack space O(log n)
4.5 Time-Space Tradeoff¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Algorithm β Time β Space β Notes β
βββββββββββββββββββββΌββββββββββββββΌββββββββββββββΌβββββββββ€
β Merge sort β O(n log n) β O(n) β Stable β
β Quick sort β O(n log n) β O(log n) β In-pl. β
β Heap sort β O(n log n) β O(1) β In-pl. β
βββββββββββββββββββββΌββββββββββββββΌββββββββββββββΌβββββββββ€
β Fibonacci (recur) β O(2βΏ) β O(n) β Poor β
β Fibonacci (memo) β O(n) β O(n) β Spaceβ β
β Fibonacci (iter) β O(n) β O(1) β Optimalβ
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5. Complexity Analysis Examples¶
Example 1: Nested Loops¶
// Analysis: What is the time complexity?
int example1(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // n times
for (int j = 0; j < n; j++) { // n times
count++;
}
}
return count;
}
// Answer: O(nΒ²)
// n Γ n = nΒ²
Example 2: Asymmetric Nested Loops¶
int example2(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // n times
for (int j = 0; j < i; j++) { // 0, 1, 2, ..., n-1 times
count++;
}
}
return count;
}
// Answer: O(nΒ²)
// 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(nΒ²)
Example 3: Logarithmic Iteration¶
int example3(int n) {
int count = 0;
for (int i = 1; i < n; i *= 2) { // logβ(n) times
count++;
}
return count;
}
// Answer: O(log n)
// i: 1, 2, 4, 8, ..., n β logβ(n) iterations
Example 4: Nested Logarithmic Iteration¶
int example4(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // n times
for (int j = 1; j < n; j *= 2) { // log n times
count++;
}
}
return count;
}
// Answer: O(n log n)
// n Γ log n
Example 5: Sequential Loops¶
int example5(int n) {
int count = 0;
for (int i = 0; i < n; i++) { // O(n)
count++;
}
for (int i = 0; i < n; i++) { // O(n)
for (int j = 0; j < n; j++) { // O(n)
count++;
}
}
return count;
}
// Answer: O(nΒ²)
// O(n) + O(nΒ²) = O(nΒ²)
// Keep only highest-order term
Example 6: Conditional Execution¶
int example6(int n, bool flag) {
int count = 0;
if (flag) {
for (int i = 0; i < n; i++) { // O(n)
count++;
}
} else {
for (int i = 0; i < n; i++) { // O(nΒ²)
for (int j = 0; j < n; j++) {
count++;
}
}
}
return count;
}
// Answer: O(nΒ²)
// Consider worst case
Example 7: Recursion Analysis¶
int example7(int n) {
if (n <= 1)
return 1;
return example7(n - 1) + example7(n - 1);
}
// Answer: O(2βΏ)
// T(n) = 2T(n-1) + O(1)
// Call tree:
// f(4)
// / \
// f(3) f(3)
// / \ / \
// f(2) f(2) f(2) f(2)
// ...
// Nodes per level: 1, 2, 4, 8, ... = 2βΏ
6. Practical Analysis Tips¶
6.1 Coding Test Time Limit Guidelines¶
For 1 second time limit (C/C++):
βββββββββββββββββ¬ββββββββββββββββββββββ
β Complexity β Maximum Input Size β
βββββββββββββββββΌββββββββββββββββββββββ€
β O(n!) β n β€ 10 β
β O(2βΏ) β n β€ 20 β
β O(nΒ³) β n β€ 500 β
β O(nΒ²) β n β€ 5,000 β
β O(n log n) β n β€ 1,000,000 β
β O(n) β n β€ 10,000,000 β
β O(log n) β n β€ 10ΒΉβΈ β
βββββββββββββββββ΄ββββββββββββββββββββββ
Python is ~10-100Γ slower than C/C++
β Reduce n by 1/10 from above guidelines
6.2 Common Operation Complexities¶
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Data Structure/Op β Average β Worst β Note β
ββββββββββββββββββββββΌββββββββββββΌββββββββββββΌβββββββββ€
β Array access β O(1) β O(1) β β
β Array search β O(n) β O(n) β β
β Array insert/del β O(n) β O(n) β Shift β
ββββββββββββββββββββββΌββββββββββββΌββββββββββββΌβββββββββ€
β Hash table access β O(1) β O(n) β Coll. β
β Hash table insert β O(1) β O(n) β Coll. β
ββββββββββββββββββββββΌββββββββββββΌββββββββββββΌβββββββββ€
β Binary search tree β O(log n) β O(n) β Skewed β
β Balanced BST β O(log n) β O(log n) β AVL β
ββββββββββββββββββββββΌββββββββββββΌββββββββββββΌβββββββββ€
β Heap insert/delete β O(log n) β O(log n) β β
β Heap min access β O(1) β O(1) β β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
6.3 Analysis Checklist¶
β‘ Identify iteration counts for all loops
β‘ Nested loops multiply complexity
β‘ Sequential loops add (keep highest order)
β‘ Analyze recursive calls with recurrence
β‘ Consider worst case for conditionals
β‘ Check library function complexity
β‘ Analyze space complexity too
7. Practice Problems¶
Problem 1: Calculate Complexity¶
Find the time complexity of the following code.
void mystery(int n) {
for (int i = n; i >= 1; i /= 2) {
for (int j = 1; j <= n; j *= 2) {
// O(1) work
}
}
}
Show Answer
**O(logΒ²n)** - Outer loop: i decreases from n to 1 by half β log n times - Inner loop: j increases from 1 to n by doubling β log n times - Total: log n Γ log n = O(logΒ²n)Problem 2: Complexity Comparison¶
Compare operation counts when n = 1000.
A. O(n)
B. O(n log n)
C. O(nΒ²)
D. O(2^(log n))
Show Answer
A. O(n) = 1,000
B. O(n log n) β 10,000
C. O(nΒ²) = 1,000,000
D. O(2^(log n)) = O(n) = 1,000
Since 2^(logβ n) = n, A and D are equal
Problem 3: Recursion Analysis¶
int f(int n) {
if (n <= 1) return 1;
return f(n/2) + f(n/2);
}
Show Answer
**O(n)** Recurrence: T(n) = 2T(n/2) + O(1) Applying Master Theorem: - a = 2, b = 2, f(n) = O(1) - n^(logβ2) = nΒΉ = n - f(n) = O(1) < n β Case 1 - T(n) = O(n)Recommended Problems¶
| Difficulty | Problem | Platform |
|---|---|---|
| β | Sort Numbers | Baekjoon |
| β | Number Search | Baekjoon |
| ββ | Two Sum | LeetCode |
| ββ | Contains Duplicate | LeetCode |
Next Steps¶
- 02_Arrays_and_Strings.md - Two pointers, sliding window
References¶
- Big-O Cheat Sheet
- VisuAlgo
- Introduction to Algorithms (CLRS)