Array — static, dynamic; cache locality; amortized O(1) append

3.2.1 · Coding › Linear Data Structures

1. Array kya hota hai?

WHY contiguous? Taaki hume kabhi store na karna pade ki agla element kahan hai — hum use compute karte hain.

2. Static vs Dynamic arrays

Key trick yeh hai: ek dynamic array do numbers store karta hai:

Term	Meaning
`size`	kitne elements tumne actually daaley hain
`capacity`	abhi kitne slots allocated hain (`capacity ≥ size`)

3. Append operation aur amortized O(1)

append(x) mein KYA hota hai:

Agar size < capacity: index size par x likho, size++ karo. → O(1) (sasta append).
Agar size == capacity: naaya block allocate karo capacity $g \cdot capacity$ ka, saare size purane elements copy karo, purana block free karo, phir likho. → O(n) (mehenga append).

Derivation: doubling amortized O(1) kyun deta hai

4. Cache locality — hidden superpower

Figure — Array — static, dynamic; cache locality; amortized O(1) append

5. Complexity summary (the 80/20 table)

Operation	Static array	Dynamic array
Access `a[i]`	O(1)	O(1)
Update `a[i]=x`	O(1)	O(1)
Append at end	n/a	O(1) amortized (O(n) worst)
Insert/delete at front/middle	O(n) (shift)	O(n) (shift)
Search (unsorted)	O(n)	O(n)
Space	O(n)	O(n), up to ~2× over-allocated

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho ek row mein identical lockers hain, numbered 0,1,2… Locker 5 kholne ke liye tum seedha wahan chale jaate ho — pehle lockers 0–4 nahi kholte. Isliye arrays ko read karna instant hai. Ab maano row bhar gayi aur tumhe ek aur locker chahiye. Tum end mein ek aur glue nahi kar sakte (wall hai wahan). Toh tum ek nayi row twice as long banate ho, saara saman wahan le jaate ho, aur continue karte ho. Yeh doubling trick karne se matlab hai ki tum saman kabhi kabhi hi move karte ho, toh on average ek locker add karna still sasta hai. Bonus: kyunki lockers ek seedhi line mein hain, jab tum locker 5 se kuch lete ho toh tumhare haath 6,7,8 ke paas already hain — computer "ek muthi mein pakad leta hai." Scattered lockers (linked list) tumhe baar baar bhaagna padata.

Flashcards

Arrays ki woh single property kya hai jo O(1) access AUR cache locality deti hai?

Contiguous memory layout with fixed-size elements.

Element i ke liye address formula derive karo.

addr(i) = B + i·s, jahan B = base address, s = element size in bytes. Element i+1, i ke s bytes baad start hota hai, toh induction se i·s add karo.

Dynamic-array append O(1) amortized kyun hai, O(1) worst-case kyun nahi?

Zyaatar appends bas write karte hain (O(1)); kabhi kabhi full array O(n) copy trigger karta hai. n appends mein average karne par total copy cost O(n) hai, toh per-append O(1) hai.

Ek dynamic array kaun se do numbers track karta hai aur woh kaise related hain?

size (elements used) aur capacity (slots allocated), jahan capacity ≥ size.

Doubling growth ke saath n appends ki total copy cost?

1+2+4+…+2^k < 2n = O(n), toh O(1) amortized.

Constant (+1) se badhana append ko O(n) amortized kyun banata hai?

Har append resize karta hai; total copies = 1+2+…+(n-1) = n(n-1)/2 = O(n²); n se divide karne par O(n) milta hai.

Cache line kya hota hai aur arrays ise exploit kyun karte hain?

~64-byte chunk jo CPU ek saath load karta hai; contiguous array elements saath mein aate hain, toh neighbours pre-loaded hote hain → kam slow RAM trips.

64-byte lines aur 4-byte ints ke liye, ek fetch mein kitne elements?

64/4 = 16 elements.

Array ke front mein insert karne ki cost?

O(n) — har element ko ek slot shift karna padta hai.

Static vs dynamic array ka key difference?

Static = allocation par fixed size; dynamic = ek bada block reallocate karke aur copy karke grow kar sakta hai.

Connections

Linked List — ulta trade-off: O(1) splice lekin poor cache locality, O(n) access.
Amortized Analysis — aggregate / accounting / potential methods doubling argument ko generalize karte hain.
Geometric Series — $\sum 2^{j} < 2 n$ bound jo O(1) append ko underpin karta hai.
CPU Cache and Memory Hierarchy — contiguity equal Big-O structures ko kyun beat karta hai.
Hash Table — dynamic arrays (buckets) use karta hai aur wahi doubling/rehash growth.
Stack (Data Structure) — typically dynamic array par implement hota hai; push = amortized O(1) append.
Big-O Notation — worst vs amortized vs average.