Time & Space Complexity

Complexity analysis is the most important skill in Competitive Programming because it helps us estimate whether our algorithm will run within the time limit.

What is Big O Notation?

Big O Notation describes how much slower an algorithm gets as the input size increases.

Analysis Examples

// O(1) - Constant Time
int getFirst(vector<int>& arr) {
    return arr[0];
}

// O(n) - Linear Time
int sum(vector<int>& arr) {
    int total = 0;
    for (int x : arr) total += x;
    return total;
}

// O(n²) - Quadratic Time
void printPairs(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;
        }
    }
}

Common Time Complexities

Ordered from fastest to slowest:

Complexity	Name	Example
$O(1)$	Constant	Array access, Hash table
$O(\log n)$	Logarithmic	Binary Search
$O(\sqrt{n})$	Square Root	Prime factorization
$O(n)$	Linear	Linear Search, loop iteration
$O(n \log n)$	Linearithmic	Merge Sort, Sort
$O(n^2)$	Quadratic	Bubble Sort, 2 nested loops
$O(n^3)$	Cubic	Matrix multiplication
$O(2^n)$	Exponential	Subset generation
$O(n!)$	Factorial	Permutation

Estimating Number of Operations

Simple rule: A computer can perform approximately $10^8$ operations per second

Reference Table

Size n	Acceptable Complexity
$n \leq 10$	$O(n!)$, $O(n^7)$
$n \leq 20$	$O(2^n)$, $O(n^5)$
$n \leq 100$	$O(n^4)$
$n \leq 500$	$O(n^3)$
$n \leq 5000$	$O(n^2)$
$n \leq 10^5$	$O(n \log n)$
$n \leq 10^6$	$O(n)$
$n \leq 10^8$	$O(\log n)$, $O(1)$

Analysis Examples

Example 1: Two Sum

// Method 1: Brute Force O(n²)
vector<int> twoSumBrute(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

// Method 2: Hash Map O(n)
vector<int> twoSumOptimal(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

Analysis:

• If $n = 10^5$:
  • Method 1: $10^{10}$ operations → TLE (Time Limit Exceeded)
  • Method 2: $10^5$ operations → Pass

Example 2: Binary Search

// O(log n) - Find position of target in sorted array
int binarySearch(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; // Not found
}

Why is it $O(\log n)$?

• Each loop iteration halves the search space
• If $n = 10^6$: only about $\log_2(10^6) \approx 20$ iterations needed

Space Complexity

Besides Time Complexity, we must also consider Memory usage.

// O(1) Space - No additional memory used
void reverseInPlace(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        swap(arr[left++], arr[right--]);
    }
}

// O(n) Space - Memory usage grows with input size
vector<int> copyReverse(vector<int>& arr) {
    vector<int> result(arr.rbegin(), arr.rend());
    return result;
}

Common Memory Limits

Limit	What can be stored
256 MB	int array size ~$6 \times 10^7$
256 MB	long long array size ~$3 \times 10^7$
256 MB	2D int array size ~$8000 \times 8000$

Common Mistakes

1. Hidden Complexity in STL

// ❌ Bad - O(n) per insertion
vector<int> v;
for (int i = 0; i < n; i++) {
    v.insert(v.begin(), i); // insert at beginning is O(n)
}
// Total O(n²)

// ✅ Better - O(1) per insertion
deque<int> d;
for (int i = 0; i < n; i++) {
    d.push_front(i); // O(1)
}
// Total O(n)

2. String Concatenation

// ❌ Bad - O(n²) due to string copy
string result = "";
for (int i = 0; i < n; i++) {
    result += to_string(i);
}

// ✅ Better - O(n)
stringstream ss;
for (int i = 0; i < n; i++) {
    ss << i;
}
string result = ss.str();

3. Parameter Passing

// ❌ Bad - copies entire vector each time
int solve(vector<int> arr) { ... }

// ✅ Better - pass by reference
int solve(vector<int>& arr) { ... }
int solve(const vector<int>& arr) { ... }

Summary

1. Analyze before coding - Estimate complexity before writing code
2. Memorize reference table - Know what complexity works for each input size
3. Watch for hidden costs - Some STL operations have hidden complexity
4. Practice analysis - The more you analyze, the better you get

💡 Tip: If unsure, calculate the actual number of operations and divide by $10^8$ to get approximate runtime