Module 2.1 ⏱ 25 min read ⚡ Linear Data Structures

Static vs. Dynamic Arrays & Amortized Analysis

Welcome to Module 2! Kick off linear structures by exploring how elements are tightly packed in continuous memory blocks and how dynamic resizing scales behind the scenes.

1. Continuous Memory Allocation & Indexing

An array stores items in contiguous blocks of RAM. Because every element occupies a fixed byte size, the computer can instantly calculate the exact memory address of any index using basic arithmetic: Base Address + (Index × Size of Data Type). This gives arrays $O(1)$ random access efficiency.

2. Static vs. Dynamic Array Mechanics

Static Arrays: Fixed size determined at compile time. You cannot append elements beyond their initial capacity.

Dynamic Arrays (e.g., C++ Vectors, Python Lists, Java ArrayLists): Automatically resize when full. When capacity is hit, the runtime allocates a brand-new contiguous block of memory (usually double the original size), copies all existing elements over, and frees the old block.

// C++ Dynamic Vector Resizing Behavior
#include <vector>
int main() {
    std::vector<int> vec;
    vec.push_back(10); // Triggers underlying memory allocation
    vec.push_back(20);
    return 0;
}
            

# Python List Dynamic Append Operations
my_list = []
my_list.append(10)  # Dynamically expands internal buffer when needed
my_list.append(20)
            

// Java ArrayList Resizing
import java.util.ArrayList;
public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(10);
    }
}
            

3. Amortized Analysis of Dynamic Append

While a single resize operation takes $O(n)$ time to copy elements, it happens infrequently. By distributing the heavy cost of resizing across all prior insertions, the amortized time complexity of an append operation becomes $O(1)$!

Quick Check: Test Your Intuition

What is the average amortized time complexity of adding an element to the end of a dynamic array?