☕ DSA Java Articles

Topics › Basics › Things to Know in C++/Java/Python or any language

Theory with examples

Easy TUF ID 1219 A2Z

Java source ↗ Edit this article ↗

What this covers

This row of the sheet is the introduction to time and space complexity: how to estimate the amount of work an algorithm does as a function of the input size, write that estimate in Big-O notation, and use it to decide, before writing any code, whether an approach will run in time. The Java file turns the theory into numbers: each method runs an algorithm while counting its basic operations, and the tests check that the counts grow exactly as the formulas predict.

Why count operations instead of seconds

Measuring seconds depends on the machine, the language and the compiler. Counting basic operations (comparisons, additions, array accesses) as a function of n describes the algorithm itself. We then keep only the term that grows fastest and drop constant factors: 3n^2 + 10n + 7 becomes O(n^2). The reason this is useful is that for large n the fastest-growing term dominates everything else, and constant factors rarely change whether a solution passes.

Three habits make the estimate quick:

  1. A loop that runs n times around constant work is O(n).
  2. Nested loops multiply: n by n is O(n^2); n by log n is O(n log n).
  3. Halving the problem each step gives O(log n) steps, because n can be halved only about log2 n times before reaching 1.

O(n): one pass

Linear search looks at elements until it finds the target. In the worst case, when the target is absent or last, it looks at all n.

static long linearSearchSteps(int[] a, int target) {
    long steps = 0;
    for (int i = 0; i < a.length; i++) {
        steps++;
        if (a[i] == target) break;
    }
    return steps;
}

The tests confirm 1 comparison in the best case, 8 for an absent target in an 8-element array, and 100000 for an array of 10^5. Big-O describes the worst case unless stated otherwise, so linear search is O(n) even though a lucky input finishes in one step.

O(log n): halving

Binary search on a sorted array compares the middle element with the target and discards half the range each probe. After k probes the range has at most n / 2^k elements, so it is empty after about log2 n probes.

static long binarySearchSteps(int[] sorted, int target) {
    long steps = 0;
    int lo = 0, hi = sorted.length - 1;
    while (lo <= hi) {
        steps++;
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] == target) break;
        if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return steps;
}

For 8 elements an absent target costs exactly floor(log2 8) + 1 = 4 probes; for 10^5 elements at most 17. Compare that with 100000 for linear search: this gap is what the whole binary-search section of the sheet is about. The same count appears in any “halve until one is left” loop:

static long halvingSteps(long n) {
    long steps = 0;
    while (n > 1) {
        n /= 2;
        steps++;
    }
    return steps;
}

halvingSteps(1024) is 10, and halvingSteps(10^12) is only 39.

O(n^2) and O(n^3): nested loops

Checking every pair with i < j runs the inner loop n - 1, n - 2, ..., 0 times, which sums to n(n - 1) / 2:

static long pairLoopSteps(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) steps++;
    }
    return steps;
}

The / 2 and the - 1 are constant-factor and lower-order details; the count is O(n^2). The test for n = 3000 compares the loop’s count with the closed form 3000 × 2999 / 2. Three nested loops give n^3 exactly:

static long tripleLoopSteps(int n) {
    long steps = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) steps++;
        }
    }
    return steps;
}

tripleLoopSteps(200) is 8 × 10^6, still fast; n = 2000 would be 8 × 10^9, which is not.

O(n log n): divide, recurse, merge

Merge sort splits the array in half, sorts each half recursively and merges in linear time. The work satisfies T(n) = T(n/2) + T(n - n/2) + n with T(1) = 0. There are about log2 n levels of splitting and each level does n work in total, hence n log n.

static long mergeSortSteps(int n) {
    if (n <= 1) return 0;
    int half = n / 2;
    return mergeSortSteps(half) + mergeSortSteps(n - half) + n;
}

For powers of two the count is exactly n log2 n: mergeSortSteps(8) is 24 and mergeSortSteps(1024) is 10240. For n = 1000 it lies between 1000 × 9 and 1000 × 10. Sorting-based solutions, heaps and balanced trees all live in this class.

O(2^n): trying every subset

Deciding, for each of n items, whether to include it or not produces a binary tree of choices with 2^n leaves, one per subset. A recursion that explores both branches visits every leaf.

static long subsetLeaves(int n) {
    if (n == 0) return 1;
    return subsetLeaves(n - 1) + subsetLeaves(n - 1);
}

subsetLeaves(20) is already 1048576. Exponential algorithms are acceptable only for tiny n (roughly up to 20 or 25), which is why problems that expect them announce it through their constraints.

Reading the constraints

A modern judge executes on the order of 10^8 simple operations per second. Combine that with the input size in the problem statement and the required complexity follows almost mechanically:

static String feasibleComplexity(long n) {
    if (n <= 20) return "O(2^n)";
    if (n <= 500) return "O(n^3)";
    if (n <= 10_000) return "O(n^2)";
    if (n <= 1_000_000) return "O(n log n)";
    if (n <= 100_000_000L) return "O(n)";
    return "O(log n) or O(1)";
}

The boundaries are rules of thumb, not laws. n ≤ 10^5 means an O(n^2) solution (10^10 steps) will time out and an O(n log n) one (about 1.7 × 10^6 steps) is comfortable. n ≤ 10^18 means you cannot even loop to n; the intended solution is logarithmic or closed-form. Make this check before designing the algorithm, so that you know what you are aiming for.

Space complexity

Space is counted the same way: the extra memory used as a function of n, ignoring the input itself. A few variables are O(1). A copy of the array or a hash map with one entry per element is O(n). A 2D table of size n × n is O(n^2). Recursion also uses memory: each active call occupies a stack frame, so a recursion n levels deep is O(n) space even if it allocates nothing, and in Java it will throw StackOverflowError somewhere around 10^4 to 10^5 levels. Many “optimal” solutions in later sections trade a little time for O(1) space, or the reverse; being able to state both costs is what the interviewer is listening for.

Edge cases and pitfalls