What does Big-O tell you, and what does it hide?

A strong answer

A strong candidate frames What does Big-O tell you, and what does it hide? around the exact memory layout, compiler semantics, and hardware execution model covered in Growth rates and Big-O. Explain the definition, why constants and smaller terms are dropped, and the real costs that can make an asymptotically better algorithm slower in practice.

The previous lesson ended with exact step counts such as n(n − 1)/2. Exact counts are more detail than you need. Take a function that does 3n² + 5n + 20 steps. At n = 1,000 that is 3,000,000 + 5,000 + 20 = 3,005,020 steps, and the n² term accounts for 99.8% of them. At a million, the other terms are a rounding error.

The constant in front, the 3, matters even less for choosing an algorithm. It changes with the language, the compiler and the machine, while the n² is a property of the algorithm itself. Double n, and any n² algorithm does four times the work, whatever its constant.

In a production interview, always connect the specification rule to its concrete runtime consequence: state what lives on the stack versus the heap or static storage segment, how the compiler or operating system validates alignments, lifetimes, and error codes, and what happens under adversarial or boundary inputs (such as zero-length buffers, integer overflow, concurrent mutation, or partial I/O). Backing your explanation with a small trace of register/memory state transitions immediately separates senior systems engineers from candidates who only memorized syntax.

What the interviewer is listening for

• Mastery of core invariant: Explain what O(f(n)) means, and why constants and smaller terms are dropped.
• Mastery of core invariant: Order the common growth rates from O(1) to O(n!).
• Mastery of core invariant: Estimate from the input size whether an algorithm will finish in time.
• Hardware and ABI awareness: Explaining how sizes, alignments, calling conventions, or kernel boundaries behave on real 64-bit targets rather than relying on implementation-defined assumptions.
• Defensive engineering: Naming the exact compiler flags (-Wall -Wextra -Werror), static analyzers, or runtime sanitizers (-fsanitize=address,undefined,thread) that verify correctness in CI.

Common mistakes

• Explaining only surface syntax without tracing the underlying memory addresses, ownership lifetime, or kernel/user-space state transitions.
• Assuming undefined behavior (such as signed overflow, uninitialized reads, strict-aliasing violations, or dangling pointers) will "just work" because it passed an unoptimized -O0 debug build.
• Ignoring return codes, partial reads/writes, alignment padding, or cleanup paths when an allocation or syscall fails midway through a function.