After this lesson, you will be able to: Explain how arrays are laid out in memory, why random access is O(1), and how dynamic arrays (JS arrays, Python lists) grow under the hood.
Arrays are the most fundamental structure and the one almost everything else is built on. Understanding why arrays are fast at some things and slow at others starts with how they sit in memory.
A classic array is a single contiguous block of memory: every element sits right next to the previous one, each taking the same number of bytes. Because of that, the computer can compute the address of element i directly: start_address + i * element_size. No scanning. That one multiplication is why reading or writing any index is O(1), called random access. It is the defining superpower of arrays.
Inserting or deleting in the middle is O(n). If you insert at index 0 of a 1000-element array, all 1000 existing elements must shift one slot to make room. Same for deletion: everything after the gap shifts back. Appending to the end is usually fast, but inserting at the front or middle is expensive precisely because the contiguous layout that makes reads fast makes shifts slow.
Memorize this table. It explains every array tradeoff.
Operation | Cost | Why-------------------------|--------|------------------------------------Access arr[i] | O(1) | Direct address mathUpdate arr[i] = x | O(1) | Direct address mathSearch for a value | O(n) | Must scan (unless sorted -> O(log n))Insert/delete at end | O(1)* | Amortized; see dynamic arrays belowInsert/delete at front | O(n) | Everything shiftsInsert/delete in middle | O(n) | Everything after the gap shifts
A true array has a fixed size. But JavaScript arrays and Python lists feel like they grow forever. They are dynamic arrays: behind the scenes they hold a fixed-capacity block, and when it fills up, they allocate a new larger block (typically double the size) and copy everything over. That copy is O(n), but because doubling happens rarely, the average cost of an append works out to O(1). That averaging is called amortized analysis: most appends are cheap, the occasional resize is expensive, and spread out it is constant.
Count the total copies across many appends.
# Capacity doubles: 1, 2, 4, 8, 16, ...# To reach n elements, total copies during resizes = 1+2+4+...+n/2 < n# So n appends cost < 2n work total -> O(1) per append on average.# Python lists, JS arrays, Java ArrayList, Go slices, C++ vector# all use this doubling strategy. Now you know why .append() is# 'usually fast but occasionally a resize happens.'
Why is reading arr[500] just as fast as reading arr[0]?
Repeatedly inserting at the front of a list in a loop (O(n) each, O(n squared) total) when a deque or appending-then-reversing would be O(n). Assuming .append() is always instant and ignoring that a huge batch triggers resizes (pre-size the array if you know the count). Confusing 'array is sorted' with 'array search is fast': search is O(n) unless you keep it sorted and use binary search. Storing a million items in a list and then doing membership checks with 'in' instead of using a set.
Sign in and purchase access to unlock this lesson.