Performance Analysis in Data Structures

Performance analysis in data structures is the process of estimating how much time and memory an operation needs as the amount of data grows. Instead of measuring seconds on one machine, we count the basic steps and the extra memory an algorithm uses, and express that count as a function of the input size n. This lets us compare data structures fairly, before writing a single benchmark.

Why Not Just Use a Stopwatch?

The obvious way to judge speed is to run the code and time it. The problem is that the result depends on things that have nothing to do with your algorithm: the CPU, other programs running, the JVM version, and even whether the JIT compiler has optimised the method yet.

A smarter question is: how does the work grow when the data grows? If a search takes 1,000 steps for 1,000 orders, will it take 2,000 steps for 2,000 orders, or barely more? That growth pattern stays the same on every machine, which is why performance analysis focuses on it.

What Performance Analysis in Data Structures Measures

Time complexity

Time complexity counts the number of basic operations, such as comparisons, assignments or array reads, as a function of n. We assume each basic operation takes roughly the same constant time, so counting them is enough.

Space complexity

Space complexity counts the extra memory the algorithm needs. It is useful to split it into two parts:

• Input space: the memory holding the data you were given.
• Auxiliary space: any additional memory the algorithm creates, such as a temporary array or the call stack used by recursion.

When people say "merge sort needs O(n) space", they mean auxiliary space. A recursive method that calls itself n levels deep also uses O(n) auxiliary space, even if it never creates an array, because every call adds a frame to the thread's stack.

Growth Rates and Big-O Notation

Exact step counts are messy, for example 3n + 7. For large inputs only the fastest-growing term matters, so we drop constants and smaller terms and keep the shape: 3n + 7 becomes O(n). This is called asymptotic analysis.

Three related notations describe bounds:

• Big-O (O): an upper bound. The algorithm grows no faster than this.
• Big-Omega (Ω): a lower bound. It grows at least this fast.
• Big-Theta (Θ): a tight bound. It is both O and Ω of the same function.

Best, Average and Worst Case

The same algorithm can do very different amounts of work depending on the input. Take a linear search through customer order IDs:

• Best case: the ID is the first one checked, so 1 step.
• Worst case: the ID is last or missing, so n steps.
• Average case: about n/2 steps if every position is equally likely, which is still O(n).

Interviewers usually ask for the worst case, because it is a guarantee: the operation will never be slower than that.

Common pitfall: treating "Big-O" and "worst case" as the same idea. They are separate. Big-O is a kind of bound; best, average and worst are scenarios. You can state the best case of quick sort with Big-O (O(n log n)) and its worst case with Big-O too (O(n²)). Mixing them up leads to answers like "quick sort is O(n log n)", which is only true for the average case.

Seeing It in Java: Counting Steps

The program below counts how many elements a linear search and a binary search examine before giving up on an ID that is not in a sorted array. Counting steps, rather than timing, gives the same answer on every computer.

public class SearchStepCounter {

    // Counts how many array elements each search looks at
    static int linearSteps(int[] orderIds, int target) {
        int steps = 0;
        for (int id : orderIds) {
            steps++;
            if (id == target) {
                break;
            }
        }
        return steps;
    }

    static int binarySteps(int[] orderIds, int target) {
        int steps = 0;
        int low = 0;
        int high = orderIds.length - 1;
        while (low <= high) {
            steps++;
            int mid = low + (high - low) / 2;   // avoids int overflow
            if (orderIds[mid] == target) {
                break;
            } else if (orderIds[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return steps;
    }

    public static void main(String[] args) {
        int[] sizes = {1_000, 1_000_000, 100_000_000};
        System.out.printf("%13s %13s %8s%n", "n", "linear", "binary");
        for (int n : sizes) {
            int[] orderIds = new int[n];
            for (int i = 0; i < n; i++) {
                orderIds[i] = i * 2;            // sorted, even IDs only
            }
            int missing = -1;                   // worst case: ID not present
            System.out.printf("%,13d %,13d %8d%n",
                    n, linearSteps(orderIds, missing), binarySteps(orderIds, missing));
        }
    }
}

            n        linear   binary
        1,000         1,000        9
    1,000,000     1,000,000       19
  100,000,000   100,000,000       26

Output from Java 21. The 100-million-element array needs about 400 MB of heap, so run the program with java -Xmx2g SearchStepCounter.

Multiplying the data by 100,000 multiplied the linear search's work by 100,000, but the binary search went from 9 steps to only 26. That is the difference between O(n) and O(log n) made visible. Binary search, however, only works on sorted data, and keeping data sorted has its own cost.

Amortized Analysis: When One Slow Operation Is Fine

Some operations are usually fast but occasionally slow. ArrayList.add() is the classic case. Internally, an ArrayList stores its elements in a plain array. When that array is full, it allocates a bigger one and copies every element across, which is an O(n) step.

What happens internally: in OpenJDK 21, the backing array starts with a capacity of 10 on the first add and then grows to about 1.5 times its size each time it fills up (newCapacity = oldCapacity + (oldCapacity >> 1)). Because each resize makes room for many more elements, the expensive copies happen rarely. Spread over all the additions, the cost per add is constant on average. This is called amortized O(1).

The growth factor is what makes this work. The simulation below counts element copies when the array grows by just one slot each time, compared with growing by 50%.

public class GrowthCopyCounter {

    // Simulates adding n elements to a growable array and counts
    // how many existing elements must be copied when it resizes.
    static long copiesWhenGrowingByOne(int n) {
        long copies = 0;
        int capacity = 10;
        for (int size = 0; size < n; size++) {
            if (size == capacity) {
                copies += size;                 // copy everything into the new array
                capacity = capacity + 1;
            }
        }
        return copies;
    }

    static long copiesWhenGrowingByHalf(int n) {
        long copies = 0;
        int capacity = 10;
        for (int size = 0; size < n; size++) {
            if (size == capacity) {
                copies += size;
                capacity = capacity + (capacity >> 1);   // grow by about 50%
            }
        }
        return copies;
    }

    public static void main(String[] args) {
        int n = 100_000;
        System.out.printf("Adding %,d elements%n", n);
        System.out.printf("Grow by 1   : %,d copies%n", copiesWhenGrowingByOne(n));
        System.out.printf("Grow by 50%% : %,d copies%n", copiesWhenGrowingByHalf(n));
    }
}

Adding 100,000 elements
Grow by 1   : 4,999,949,955 copies
Grow by 50% : 213,413 copies

Growing by one slot turns 100,000 additions into nearly five billion copies, which is O(n²) in total. Growing by a fixed percentage keeps the total near 2n, which is O(n) in total and O(1) per addition. If you already know roughly how many elements you will store, new ArrayList<>(expectedSize) avoids the resizes altogether.

Hidden Costs Big-O Does Not Show

Big-O hides constant factors, and in Java some of them are large:

• Boxing: an ArrayList<Integer> stores references to Integer objects, not raw int values. Each element costs an object header plus a pointer, and reading it means following that pointer. An int[] with the same O(n) complexity is often several times faster and smaller.
• Cache locality: arrays keep elements next to each other in memory, so the CPU reads them efficiently. Linked lists scatter nodes across the heap, so a traversal is O(n) for both but noticeably slower for the list.
• Bad hash codes: HashMap.get() is O(1) on average, but if many keys share a bucket it degrades. Since Java 8, a bucket with 8 or more entries is converted into a balanced tree (once the table has at least 64 buckets), which limits that bucket's lookups to O(log n) instead of O(n).

Related Tutorials

• Time complexity explained
• Space complexity explained
• Binary search in Java
• How ArrayList works internally
• HashMap in Java

Conclusion

Performance analysis in data structures gives you a machine-independent way to predict how code behaves as data grows. Count steps and extra memory, express them with Big-O, and be clear about which case you mean: best, average or worst. Remember amortized cost for structures like ArrayList, and keep an eye on the constant factors Big-O ignores. With these tools you can choose the right data structure before performance becomes a problem.