SyntaxPilot
Courses/DSA and Coding Problems/Lesson 1

DSA and Coding Problems · Lesson 1 of 90 · 11 min

Big-O and reading constraints: which complexity fits the time limit

queued

These are the notes for DSA episode 1. Before solving any coding problem you need one skill: predicting whether your solution is fast enough before you run it. You will learn why correct code gets Time Limit Exceeded, what Big-O notation measures, the rules for working it out, how to read a problem's constraints, and how sorting turns a slow duplicate check into a fast one. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem: correct code that still fails

A placement test asks: a college has a list of roll numbers; does any roll number appear twice? You write the obvious solution, it passes the sample with 5 roll numbers, you submit, and the judge says Time Limit Exceeded (TLE). The hidden test had 500,000 roll numbers.

The code was correct. It was just too slow. Online judges always include hidden tests with the largest input the constraints allow, so "it works on the sample" proves nothing about speed.

The brute force: compare every pair

public class Main {
    static boolean hasDuplicate(int[] roll) {
        for (int i = 0; i < roll.length; i++)
            for (int j = i + 1; j < roll.length; j++)
                if (roll[i] == roll[j]) return true;
        return false;
    }
    public static void main(String[] args) {
        for (int n : new int[]{10000, 20000, 40000, 80000}) {
            int[] roll = new int[n];
            for (int i = 0; i < n; i++) roll[i] = (int) (i * 7919L % 1000003);
            long start = System.nanoTime();
            boolean dup = hasDuplicate(roll);
            long ms = (System.nanoTime() - start) / 1000000;
            System.out.println("n = " + n + "   dup: " + dup + "   " + ms + " ms");
        }
    }
}

Output (times vary from machine to machine and run to run):

n = 10000   dup: false   24 ms
n = 20000   dup: false   73 ms
n = 40000   dup: false   166 ms
n = 80000   dup: false   617 ms

i * 7919L % 1000003 just fills the array with distinct numbers in a scrambled order, so there is no duplicate and the loops never stop early: the worst case. Each time n doubles, the time grows by much more than double. With n = 500000 the judge reports:

Time Limit Exceeded (8 s)

Why it is slow: count the work

With n roll numbers there are n(n-1)/2 pairs.

n Pairs compared
10,000 about 50 million
80,000 about 3.2 billion
500,000 about 125 billion

Rule of thumb: a computer does roughly 10⁸ (100 million) simple steps per second. It can be a few times faster or slower, but it is the right ballpark for planning. 125 billion steps is minutes of work. No faster machine fixes this; the problem is how the work grows.

Big-O: how the work grows

Big-O notation describes how the number of steps grows as the input size n grows, ignoring the details of the machine.

Big-O Name Real-life example n = 100,000
O(1) constant open locker number 42: walk straight to it 1 step
O(log n) logarithmic find a word in a dictionary by halving about 17 steps
O(n) linear a delivery boy visits every house once 100,000 steps
O(n log n) linearithmic sorting about 1.7 million steps
O(n²) quadratic every wedding guest shakes every hand 10 billion steps: TLE
O(2ⁿ) exponential try every subset astronomically many

The rules

  1. Count steps as a function of n, the input size.
  2. Drop constants: 3n + 5 is O(n).
  3. Keep the biggest term: n² + n is O(n²).
  4. Loops one after another add: n + n is still O(n).
  5. Loops inside loops multiply: n × n is O(n²).
  6. A loop that halves or doubles its counter runs log n times.
  7. Big-O usually means the worst case for large n, because that's what the judge sends.

Checking the rules live

public class Main {
    public static void main(String[] args) {
        int n = 1000;
        long one = 0, nested = 0, halving = 0;
        for (int i = 0; i < n; i++) one++;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) nested++;
        for (int i = 1; i < n; i *= 2) halving++;
        System.out.println("single loop:  " + one);
        System.out.println("nested loops: " + nested);
        System.out.println("halving loop: " + halving);
    }
}

Output:

single loop:  1000
nested loops: 1000000
halving loop: 10

2¹⁰ = 1024, so a doubling loop up to 1000 runs 10 times: log₂ 1000 ≈ 10.

Reading constraints

Every problem states the maximum n. Combine it with the 10⁸ rule and the constraints tell you which complexity to aim for:

Constraint Complexity that fits Typical technique
n ≤ 10 O(n!) try every order (permutations)
n ≤ 20 O(2ⁿ) try every subset, bitmasks
n ≤ 500 O(n³) three nested loops, Floyd-Warshall
n ≤ 5,000 O(n²) every pair, simple DP
n ≤ 10⁵ to 10⁶ O(n log n) sorting, binary search, heaps
n ≤ 10⁸ O(n) one pass, two pointers
n up to 10¹⁸ O(log n) or O(1) math, binary search on the answer

Our test had n = 500,000, so O(n²) could never pass. We need O(n log n) or better.

The fix: sort, then compare neighbours

After sorting, equal numbers sit next to each other, so one pass comparing each element with the one before it finds any duplicate.

import java.util.Arrays;
public class Main {
    static boolean hasDuplicate(int[] roll) {
        Arrays.sort(roll);
        for (int i = 1; i < roll.length; i++)
            if (roll[i] == roll[i - 1]) return true;
        return false;
    }
    public static void main(String[] args) {
        for (int n : new int[]{10000, 80000, 500000, 1000000}) {
            int[] roll = new int[n];
            for (int i = 0; i < n; i++) roll[i] = (int) (i * 7919L % 1000003);
            long start = System.nanoTime();
            boolean dup = hasDuplicate(roll);
            long ms = (System.nanoTime() - start) / 1000000;
            System.out.println("n = " + n + "   dup: " + dup + "   " + ms + " ms");
        }
    }
}

Output:

n = 10000   dup: false   5 ms
n = 80000   dup: false   9 ms
n = 500000   dup: false   54 ms
n = 1000000   dup: false   72 ms

Edge cases:

System.out.println(hasDuplicate(new int[]{42, 7, 19, 7, 88}));   // true
System.out.println(hasDuplicate(new int[]{5}));                  // false
System.out.println(hasDuplicate(new int[]{}));                   // false

With 0 or 1 elements the loop from index 1 never runs: no comparisons, no crash.

Brute force vs optimal

Approach Time Extra space n = 500,000
Compare every pair O(n²) O(1) Time Limit Exceeded
Sort + compare neighbours O(n log n) O(log n) (in-place sort) about 50 ms
HashSet of seen values (episode 2) O(n) average O(n) fastest

The same solution in C++ and Python

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

bool hasDuplicate(vector<int> roll) {          // a copy: the caller's vector is not changed
    sort(roll.begin(), roll.end());
    for (size_t i = 1; i < roll.size(); i++)
        if (roll[i] == roll[i - 1]) return true;
    return false;
}

int main() {
    cout << boolalpha << hasDuplicate({42, 7, 19, 7, 88}) << "\n";   // true
    cout << hasDuplicate({5}) << "\n";                                  // false
}
def has_duplicate(roll):
    roll = sorted(roll)                 # a new sorted list: O(n) extra space
    for i in range(1, len(roll)):
        if roll[i] == roll[i - 1]:
            return True
    return False

print(has_duplicate([42, 7, 19, 7, 88]))   # True
print(has_duplicate([5]))                  # False

Space complexity

Space complexity counts the extra memory a solution uses, as a function of n. The brute force uses two loop variables: O(1). Arrays.sort on an int[] sorts in place (a small O(log n) stack). But in place means the caller's array is changed; if the original order matters, copy it first (O(n) space). In the C++ and Python versions above, the function sorts a copy.

Common mistakes

Mistake What you see Why Fix
int pairs = n * n; with n = 100000 prints 1410065408 int holds at most 2,147,483,647; the product overflows silently (long) n * n prints 10000000000
list.contains(x) inside a loop Time Limit Exceeded contains walks the whole list: O(n) inside O(n) = O(n²) use a HashSet
s = s + c; in a loop Time Limit Exceeded each + copies the whole String: O(n²) use a StringBuilder
"It passed the sample" TLE on hidden tests samples are tiny; hidden tests use the maximum n check Big-O against the constraints first

The overflow, run live:

int n = 100000;
System.out.println(n * n);          // 1410065408
System.out.println((long) n * n);   // 10000000000

Mini project: will it pass?

For each pair (code, constraint), decide whether it passes in about 1 second before running it:

Code Constraint Steps Verdict
two nested loops n ≤ 2,000 4 × 10⁶ passes
two nested loops n ≤ 2 × 10⁵ 4 × 10¹⁰ TLE
sort + one loop n ≤ 10⁶ 2 × 10⁷ passes
three nested loops n ≤ 500 1.25 × 10⁸ passes (just)
try every subset n ≤ 40 10¹² TLE

Practice

  1. What is the Big-O of for (i = 0; i < n; i++) for (j = 0; j < i; j++) count++;?
Solution

The inner loop runs 0 + 1 + 2 + ... + (n - 1) = n(n-1)/2 times. Drop constants and smaller terms: O(n²). Half of n² is still n².

  1. A problem has n ≤ 2000. Will an O(n²) solution pass? What about n ≤ 2 × 10⁵?
Solution

2000² = 4 × 10⁶ steps: easily passes. (2 × 10⁵)² = 4 × 10¹⁰: about 400 seconds at 10⁸ steps per second, so TLE. You need O(n log n) or better.

  1. How many times does for (int i = 1; i < n; i *= 3) run for n = 1,000,000?
Solution

i takes the values 1, 3, 9, ..., 3¹² = 531,441 (3¹³ = 1,594,323 is too big), so 13 times: log₃ n. It is still O(log n): the base of the log is a constant.

  1. Find the largest gap between two neighbouring values after sorting, for [9, 2, 30, 14].
Solution
int[] a = {9, 2, 30, 14};
Arrays.sort(a);                       // 2, 9, 14, 30
int gap = 0;
for (int i = 1; i < a.length; i++) gap = Math.max(gap, a[i] - a[i - 1]);
System.out.println(gap);              // 16

O(n log n) time.

Quick quiz

What is the time complexity?

for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < n; j++) {
        count++;
    }
}
  • O(n)
  • O(log n)
  • O(n log n)
  • O(n²)
Answer

O(n log n). The outer loop doubles i, so it runs about log n times; the inner loop runs n times for each. Nested loops multiply.

Interview questions

  1. What does Big-O measure? How the running time (or memory) grows as the input size grows, for large inputs, ignoring constant factors.
  2. Why do we drop constants? For large n, a constant factor doesn't change which algorithm wins: an O(n) algorithm with a big constant still beats O(n²) once n is large.
  3. Is O(n log n) always slower than O(n)? For large enough n, yes, but for small inputs constants matter and an "O(n log n)" sort can beat a heavy O(n) method.
  4. What is the difference between time and space complexity? Time counts steps; space counts extra memory beyond the input.
  5. How do you choose an approach in a contest? Read the constraints, compute roughly how many steps each idea needs, and compare with about 10⁸ per second.
  6. Best, average and worst case? Big-O usually refers to the worst case (an upper bound). Hash table lookups are O(1) on average but O(n) in the worst case.

Glossary

Term Meaning
Algorithm A step-by-step method for solving a problem
Brute force Trying every possibility directly, without a clever idea
Time Limit Exceeded (TLE) The judge stopped your program because it ran longer than allowed
Hidden test A judge's test you can't see, usually with the largest allowed input
Constraints The limits a problem promises on its input, like n ≤ 10⁵
Input size (n) How big the input is: the number of elements, characters, etc.
Time complexity How the number of steps grows with n
Space complexity How the extra memory grows with n
Big-O notation A way to write that growth, keeping only the biggest term: O(n²)
Constant time, O(1) The same work no matter how big n is
Logarithmic, O(log n) Work grows by one step every time n doubles (halving)
Linear, O(n) Work grows in proportion to n
Quadratic, O(n²) Work grows with the square of n: every pair
Worst case The input that makes the algorithm do the most work
In place Changes the input directly, using little extra memory
Integer overflow A result too big for its type wraps around to a wrong value, with no error

Summary

  • Correct but slow code fails with Time Limit Exceeded on the hidden maximum-size test.
  • Big-O describes how work grows with n: drop constants, keep the biggest term, nested loops multiply, halving gives log n.
  • Plan with about 10⁸ simple steps per second, and read the constraints first: n ≤ 10⁵ means O(n log n) or better.
  • Sorting first puts duplicates side by side: O(n log n) instead of O(n²).
  • Watch for int overflow when n is big: use long.

Next episode: Two Sum, and the HashMap trick that does lookups in O(1).