Growth Rates and Reading Constraints

1.The ladder of growth rates

From fastest to slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) (good sorting), O(n²) quadratic (all pairs), O(n³) cubic (all triples), O(2ⁿ) exponential (all subsets), O(n!) factorial (all orderings).

The gaps are enormous. For n = 100,000: log n ≈ 17, n log n ≈ 1.7 million, n² = 10 billion.

public class Main {
    public static void main(String[] args) {
        long[] sizes = {10, 1_000, 100_000};
        for (long n : sizes) {
            double log = Math.log(n) / Math.log(2);
            System.out.printf("n=%-7d log=%-5.0f nlogn=%-10.0f n2=%d%n", n, log, n * log, n * n);
        }
    }
}

n=10      log=3     nlogn=33         n2=100
n=1000    log=10    nlogn=9966       n2=1000000
n=100000  log=17    nlogn=1660964    n2=10000000000

2.Turning constraints into a target

A typical judge allows about 1 second, and Java does roughly 10⁸ simple steps per second. Divide, and the constraint tells you the slowest complexity that still passes:

n ≤ 10 → O(n!) is fine (try every order). n ≤ 20 → O(2ⁿ) (try every subset). n ≤ 500 → O(n³). n ≤ 5,000 → O(n²). n ≤ 10⁵ to 10⁶ → O(n log n) or O(n). n ≤ 10⁹ or more → O(log n) or O(1), usually maths or binary search on the answer.

So before designing anything, read the constraints and write down your target. It rules out whole families of ideas immediately.