Because elements are stored contiguously and all the same size, so the address of a[i] is a single arithmetic computation: base + i * sizeof(element). The CPU computes that offset and issues one memory access, no scanning, no traversal, independent of i and of the array's length. That constant-time random access is the defining advantage of arrays and the reason they're the substrate for so many other structures (ring buffers, hash tables, heaps). The flip side of that same contiguity is that inserting in the middle is O(n), because keeping elements contiguous forces you to shift everything after the insertion point.
Data Structures & Algorithms · Interview question
Why is array indexing O(1)?
A strong answer
What a weak answer sounds like
You know the answer. Do you know what gets you dinged?
Pro breaks down the answer most candidates actually give to this question — and the specific reason an interviewer marks it down. It’s the difference between sounding correct and sounding senior, on all 472 questions.
From the lesson
Arrays & Memory Layout
Contiguous storage is why arrays give O(1) indexing and why row-major traversal is cache-friendly, plus array-of-structs vs struct-of-arrays for embedded data.
More Arrays & Memory Layout questions
Two nested loops summing a matrix have the same Big-O but different runtimes. Why?How is a 2D array laid out in memory in C, and how do you index a flat buffer as 2D?What's the difference between array-of-structs and struct-of-arrays, and when does each win?When is an array the wrong data structure?
Browse all 472 interview questions