Time Complexity — Making Your Code Fast

Real-world analogy

What is it?

Time complexity is a way to measure how fast an algorithm is by counting how the number of operations grows as the input gets bigger. We use Big O notation — O(1), O(n), O(n log n), O(n²), etc. Understanding time complexity is crucial for competitive programming because it tells you whether your solution will pass within the time limit before you even submit it!

Real-world relevance

Google searches billions of web pages in milliseconds because they use O(1) lookups (hash tables) and O(log n) searches. If they used O(n) search, looking through billions of pages would take minutes! Amazon's recommendation system, GPS navigation, and even Netflix's movie suggestions all depend on fast algorithms with good time complexity.

Key points

• What is Time Complexity? — Time complexity measures how many operations your program performs as the input size (n) grows. It's NOT about actual seconds — it's about the PATTERN of growth. Does your program do n operations? n² operations? We care about the big picture, not exact counts.
• Big O Notation — Big O notation describes the WORST-CASE growth rate. O(n) means operations grow linearly with input. O(n²) means if input doubles, operations QUADRUPLE. We drop constants and lower terms: 3n + 5 is just O(n), and 2n² + 100n is O(n²). Only the biggest term matters!
• O(1) — Constant Time — The program does the same amount of work no matter how big the input. Example: checking if a number is even (n % 2 == 0). Whether n is 5 or 5 billion, it's one operation. O(1) is the dream — instant!
• O(n) — Linear Time — Operations grow proportionally with input. One loop through n elements is O(n). Finding the maximum in an array by scanning each element once is O(n). If n doubles, time doubles. For n ≤ 10^6 or 10^7, O(n) usually passes.
• O(n log n) — The Sweet Spot — Sorting algorithms like merge sort and C++'s sort() are O(n log n). It's faster than O(n²) but slower than O(n). For n = 1,000,000: n² = 10^12 (way too slow), but n log n ≈ 20,000,000 (fast!). Many CP problems are designed to be solved in O(n log n).
• O(n²) — Quadratic Time — Two nested loops over n elements is O(n²). For n = 1000: n² = 1,000,000 (fine). For n = 100000: n² = 10^10 (WAY too slow, TLE!). O(n²) is OK for small constraints but dangerous for large ones.
• Why TLE Happens — Time Limit Exceeded (TLE) means your program is too slow. Most judges allow about 10^8 simple operations per second. If n = 10^5 and your solution is O(n²), that's 10^10 operations — 100x too slow! You need a faster algorithm, like O(n log n) or O(n).
• Reading Constraints to Choose Your Approach — n ≤ 10: any approach works, even O(2^n). n ≤ 100: O(n³) is fine. n ≤ 1000: O(n²) works. n ≤ 10^5: need O(n log n). n ≤ 10^6-10^7: need O(n). This is the MOST USEFUL thing in competitive programming — constraints tell you the solution!
• Space Complexity (Bonus) — Just like time complexity measures operations, space complexity measures memory. An array of size n uses O(n) space. A 2D array n×n uses O(n²) space. Memory limits are usually 256MB, which is roughly 64 million integers. Keep this in mind for large inputs!

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // O(1) — Constant: always same number of operations
    cout << "First element: " << a[0] << "\n";
    
    // O(n) — Linear: one loop through all elements
    long long sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    cout << "Sum: " << sum << "\n";
    
    // O(n log n) — Sorting
    sort(a.begin(), a.end());
    cout << "Sorted min: " << a[0] << " max: " << a[n-1] << "\n";
    
    // O(n^2) — Two nested loops (SLOW for large n!)
    // Count pairs with equal values
    int pairCount = 0;
    if (n <= 5000) {  // Only safe for small n!
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] == a[j]) pairCount++;
            }
        }
    }
    cout << "Equal pairs: " << pairCount << "\n";
    
    // O(n) way to count equal pairs (SMART!)
    // After sorting, count consecutive equal elements
    int smartCount = 0;
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && a[j] == a[i]) j++;
        int groupSize = j - i;
        smartCount += groupSize * (groupSize - 1) / 2;  // Choose 2 from group
        i = j;
    }
    cout << "Equal pairs (fast): " << smartCount << "\n";
    
    return 0;
}

Line-by-line walkthrough

1. 1. We read an array of n integers — this is the standard CP input pattern.
2. 2. cout << a[0] — accessing one element is O(1). No matter how big the array, getting one element is instant.
3. 3. The sum loop: for (int i = 0; i < n; i++) sum += a[i]; — we visit each element exactly once, so it's O(n). If n doubles, the time doubles.
4. 4. sort(a.begin(), a.end()); — C++'s built-in sort is O(n log n). It's one of the most commonly used operations in CP. After sorting, the smallest is at a[0] and largest at a[n-1].
5. 5. The double loop for counting pairs: two nested loops each going up to n, so the inner loop runs roughly n²/2 times total. That's O(n²). We guard it with if (n <= 5000) to prevent TLE.
6. 6. The SMART O(n) approach: after sorting, equal elements are next to each other. We count each group's size and use the formula groupSize * (groupSize - 1) / 2 (combinations of 2 from the group). This replaces O(n²) with O(n)!
7. 7. groupSize * (groupSize - 1) / 2 — this is the combination formula 'n choose 2', which counts how many pairs you can make from groupSize elements. Math saves the day!

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    
    // Find if any two elements sum to 1000000
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i] + a[j] == 1000000) {
                cout << "YES\n";
                return 0;
            }
        }
    }
    cout << "NO\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Big O Notation — Simply Explained (NeetCode)
• Time Complexity for Competitive Programming (GeeksforGeeks)
• Problems Sorted by Difficulty (Codeforces)