Arrays and complexity analysis
A data structure is a way of organising data so that the operations you need are efficient. The array is the simplest and most fundamental, and it is the ideal place to learn how to measure efficiency.
What a data structure is
A data structure stores a collection of values together with operations on them, such as insert, delete, search, and access by position. An abstract data type (ADT) describes what operations exist and what they mean, such as a list or a queue; a data structure is a concrete way to implement it. The same ADT can have several implementations with very different costs.
Static arrays
An array stores elements in one contiguous block of memory, each the same size. Element i lives at address base + i x size, so reading or writing any element by index takes constant time, O(1), no matter how big the array is. This direct addressing is the array's great strength, and contiguity also makes arrays very cache-friendly.
The cost of insertion and deletion
Because elements are packed side by side, inserting at position i means shifting every later element one place right, and deleting means shifting them left. In the worst case, at the front, that is n moves, so insertion and deletion are O(n). Adding or removing at the end, by contrast, needs no shifting.
Searching an array
Finding a value in an unsorted array requires a linear scan, O(n). If the array is kept sorted, binary search finds a value in O(log n) by repeatedly halving the range. Keeping it sorted, however, makes insertion cost O(n), a classic trade-off between fast queries and fast updates.
Asymptotic analysis
We describe cost by how it grows with n, ignoring constant factors. Big O (O) gives an upper bound, Big Omega (Omega) a lower bound, and Big Theta (Theta) a tight bound. We usually analyse the worst case, sometimes the average case, and, for structures with occasional expensive operations, the amortised cost per operation over a long sequence.
Space and the memory model
Data structures also cost memory. An array of n 8-byte integers uses about 8n bytes plus a small header. Structures with pointers, such as linked lists, add overhead per element. Real performance also depends on caches: scanning contiguous memory can be many times faster than following pointers scattered around memory, even when both are O(n).
Multidimensional arrays
A two-dimensional array, such as an image or a matrix, is usually stored in row-major order: all of row 0, then row 1, and so on, so element (r, c) of a table with C columns is at position r x C + c. Looping over rows in the outer loop and columns in the inner loop follows memory order and is fastest; reversing the loops can be far slower on large arrays.
Worked example
An array of 1,000,000 sorted student IDs. Looking up ID number 750,000 by index: one step. Searching for a given ID value: binary search needs at most about 20 comparisons, since 2^20 is about a million, while a linear scan could need a million. Inserting a new smallest ID at the front: about 1,000,000 shifts. Choosing a structure means weighing which operations happen most.
Key takeaways
An ADT specifies operations; a data structure implements them. Arrays store elements contiguously, giving O(1) access by index and good cache behaviour. Inserting or deleting in the middle costs O(n) because of shifting. Unsorted search is O(n); sorted arrays allow O(log n) binary search but slower insertion. Big O, Omega, and Theta describe growth; analyse worst, average, or amortised costs. Memory layout and caches matter in practice. 2D arrays are usually row-major.
Flashcard
Organised storage with efficient operations
Check your understanding
Why can an array return its 500,000th element as quickly as its first?