Algorithms from zero
The array
Imagine a row of numbered boxes, each holding one value. Your array is exactly that: a sequence of boxes in memory, all lined up next to each other. This simplicity is the source of the array’s power. Because the boxes are contiguous, the computer can find any box instantly.
After this lesson you can visualize an array as contiguous memory, explain why indexing is O(1), measure the time cost of read, write, search, insert, delete, and append operations, and recognize why the array’s strength (fast random access) and weakness (slow middle insert) come from the same fact: contiguity.
An array is a sequence of elements stored in contiguous memory. “Contiguous” means the elements sit next to each other — box 0 at address 1000, box 1 at address 1004, box 2 at address 1008, and so on. Each element takes the same size (e.g., 4 bytes for a 32-bit number).
Why contiguity matters: The computer can calculate the address of any element using a simple formula:
address of element[i] = base_address + (i × element_size)For example, if the array starts at memory address 1000 and each element is 4 bytes:
array[0]is at 1000 + (0 × 4) = 1000array[1]is at 1000 + (1 × 4) = 1004array[5]is at 1000 + (5 × 4) = 1020
The computer jumps straight to address 1020 without reading any other element. That is O(1).
Array operations and their costs:
-
Read or write by index — O(1). Calculate the address, fetch or store the value. Done.
-
Search for a value — O(n). You do not know which index holds your target, so you scan from the start until you find it (or reach the end). In the worst case, you check every element.
1
function search(arr, target) {
2
for (let i = 0; i < arr.length; i++) {
3
if (arr[i] === target) return i;
4
}
5
return -1; // not found
6
}
- L2 Loop through every element (O(n) worst case)
- L3 O(1) index lookup inside the loop
-
Insert in the middle — O(n). To insert at index 3, you must shift all elements at indices 3, 4, 5, … one step to the right to make room. If the array has 100 elements, you shift ~97 elements. Shifting is the cost.
-
Delete from the middle — O(n). Same as insert: you must shift all elements after the deleted index one step left to close the gap.
-
Append to the end — O(1) amortized. Just place the new element at the next empty spot. No shifting needed (unless the array runs out of capacity, which happens rarely).
The crux: contiguity gives you O(1) reading, but O(n) writing in the middle. This is the array’s fundamental tradeoff.
Dynamic vs. fixed-size arrays:
A fixed-size array has a capacity set at creation time. Once full, you cannot add more elements.
A dynamic array (like JavaScript arrays) grows automatically. When it runs out of space, it allocates a larger block, copies all elements to it, then deallocates the old block. The cost of this copy is O(n), but it happens rarely — only when capacity is exhausted. If the array doubles its capacity each time, you spread the copying cost thinly over many appends. We say the average cost per append is O(1) amortized.
Let us code the basic array operations:
O(1) indexing:
function get(arr, i) {
return arr[i]; // Instant: calculate address, return value
}O(n) linear search:
function search(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1; // Not found
}O(n) insert at index i:
function insertAt(arr, i, value) {
// Shift all elements from index i onward one step right
for (let j = arr.length - 1; j >= i; j--) {
arr[j + 1] = arr[j];
}
// Place the new value
arr[i] = value;
}The shifting loop runs from the end backward (to avoid overwriting). For an array of 100 elements, inserting at index 0 shifts all 100 elements. For an array of 1000 elements, inserting at index 0 shifts all 1000. That is O(n).
Try calling these functions:
Watch the insertAt function step by step. We are inserting the value 25 at index 2 in the array [10, 20, 30, 40]:
1
function insertAt(arr, i, value) {
2
for (let j = arr.length - 1; j >= i; j--) {
3
arr[j + 1] = arr[j];
4
}
5
arr[i] = value;
6
}
Here is the time complexity table for array operations:
| Operation | Example | Time |
|---|---|---|
| Get element | arr[5] | O(1) |
| Set element | arr[5] = 99 | O(1) |
| Search for value | search(arr, 99) | O(n) |
| Insert at index i | insertAt(arr, 2, 50) | O(n) |
| Delete at index i | deleteAt(arr, 2) | O(n) |
| Append (push) | arr.push(99) | O(1) amortized |
Why is append O(1) amortized? In a dynamic array, append is free as long as there is spare capacity. When capacity is exhausted, the array doubles in size and copies all n elements (O(n) work). But it only has to do this once per n appends. Spread over n operations, the copying cost averages to O(1) per append.
The core insight: Random access is cheap. Sequential modification is expensive. This makes arrays ideal for read-heavy workloads and terrible for frequent insertion in the middle.
An array of 1000 elements is stored starting at memory address 2000. Each element takes 8 bytes. What is the memory address of array[10]?
Why is reading array[i] always O(1), even for very large arrays?
You want to insert a new element at index 0 of an array with 500 elements. How many elements must shift?
What does 'amortized O(1)' mean for appending to a dynamic array?
Arrange these array operations from fastest to slowest (best to worst time complexity):
- Append to end (dynamic array)
- Read element by index
- Search for a value
- Insert at the beginning
Edge cases
Fixed-size arrays run out of space. If an array has capacity 4 and you try to append a 5th element, you get an error or lose the element (in a fixed-size language like C). JavaScript arrays are always dynamic — they grow silently. But the growth is not free; it costs O(n) work. That cost is why append is O(1) “amortized” and not O(1) always.
Common mistake
Confusing array size with cost. Inserting into an array of 10 elements is much faster than inserting into an array of 1 million elements. But both are “O(n)”. Do not think O(n) means “any time is fine”; it means the time grows proportionally to n. For 1 million elements, you really will shift 1 million times.
Why does the contiguity of an array (elements stored next to each other in memory) lead to both its strength and weakness?
An array is a row of contiguous memory boxes, all the same size.
Key facts:
- Contiguous memory: Elements sit next to each other, enabling address calculation:
base + (index × element_size). - O(1) read and write: Looking up or modifying an element by index takes constant time—no scanning.
- O(n) search: Finding a value requires scanning elements one by one (worst case: all n).
- O(n) insert/delete in middle: Must shift all elements after the change point, linear in the worst case.
- O(1) amortized append: Free most of the time; rarely triggers a resize, cost spread thinly.
- The tradeoff: Contiguity gives fast access but slow middle modification. Choose arrays for read-heavy tasks.
Next, you will learn patterns that exploit this knowledge: how to search faster (binary search), how to modify faster (two pointers, sliding window), and when to use other structures (lists, queues) instead.