Array Operations and Complexity

Access by index: O(1) (random access via address arithmetic). Search (unsorted): O(n) linear scan; (sorted): O(log n) with binary search. Insertion/deletion at the END of a dynamic array: O(1) amortized; at an arbitrary position: O(n) because elements must shift. Inserting at the BEGINNING is worst case—every element shifts, O(n). Memory aid: 'arrays are cheap to read, expensive to reshape.' Updating an element in place is O(1). The fixed-size limitation forces O(n) resizing in static arrays. Contrast with linked lists, which give O(1) insert/delete at a known node but O(n) access. GATE frequently tests this access-vs-modify tradeoff.

You append a million items to a Java ArrayList and the average time per append is constant. Yet somewhere inside, the array had to be reallocated and every existing element copied — multiple times. How can a sometimes-expensive operation have a constant average cost? The answer is amortized analysis, and the dynamic-array doubling trick is the cleanest example in all of algorithms.

Definition: A dynamic array is a contiguous array that grows automatically when it runs out of space, hiding the resize from the caller. C++ std::vector, Java ArrayList, Python list, and Go slice are all dynamic arrays.

Definition: Amortized cost is the cost of an operation averaged over a worst-case sequence of operations. It is not the same as the average-case cost, which depends on a probability distribution over inputs.

The growth strategy that makes everything work

When a dynamic array is full and a new append arrives, the implementation:

1. Allocates a new buffer of larger capacity.
2. Copies all n current elements to the new buffer.
3. Frees the old buffer.
4. Appends the new element to the new buffer.

The cost of one such resize is O(n) — every element must be copied. If we did this on every single append, total cost across n appends would be 1 + 2 + 3 + ... + n = O(n²), and the per-append cost would be O(n). That is unacceptable.

The trick is to double the capacity each time the array fills up. Now a resize happens only when the current size hits a power of 2.

The geometric-series argument

Suppose we start with capacity 1 and append n elements. Resizes happen at sizes 1, 2, 4, 8, ..., up to roughly n. The cost of the resize at size 2^i is 2^i (we copy 2^i elements). Summing all resize costs:

1 + 2 + 4 + 8 + ... + n ≤ 2n

This is a geometric series with ratio 2. The total resize work across all n appends is bounded by 2n, which is O(n). Add the n cheap append steps (one assignment each), and the grand total is 3n = O(n).

Per append, the amortized cost is total / n = O(1). A constant. That is the entire payoff.

You can also derive this the other way around: the cost of n appends is total = n + n/2 + n/4 + n/8 + ... < 2n if you write the series starting from the final resize and counting backwards. Same answer, same logic.

Why doubling, and not adding a constant?

What if, instead of doubling, we grew the array by a constant amount c each time (say, c = 10)? The number of resizes would be roughly n/c, and the i-th resize would cost i × c elements copied. Total resize work:

c × (1 + 2 + 3 + ... + n/c) = c × (n/c)(n/c + 1)/2 ≈ n²/(2c)

That is O(n²) total, or O(n) per append amortized — disastrously worse. Constant-amount growth turns a near-free operation into a quadratic-time disaster on long sequences.

This is why every modern dynamic-array implementation uses geometric growth. The growth factor does not have to be 2 — C++ vector implementations have used 1.5, Python list uses about 1.125 with offsets, Java ArrayList uses 1.5 — but the principle is identical. As long as the new capacity is a constant multiple greater than the old, the geometric series converges to O(n) total work.

Why it matters: Algorithmic correctness alone does not make a data structure usable. The asymptotic constant matters in practice, and the geometric growth factor is a knob real implementations tune to balance memory waste (a larger factor wastes more) against re-copy frequency (a smaller factor copies more often).

Three flavours of amortized analysis

Amortized analysis can be done three different ways, all yielding the same answer:

• Aggregate method: Sum the total cost of n operations, divide by n. This is what we just did with the geometric series.
• Accounting method: Charge each cheap append a small extra "credit" that pays for future resizes. Show that the credits accumulated by the time a resize is needed exactly cover its cost. For doubling, each append banks 3 units of credit; when a resize from m to 2m happens, the m credits banked since the last resize cover the m copy operations.
• Potential method: Define a potential function Φ that measures stored work. Show that amortized cost = actual cost + ΔΦ ≤ constant for every operation.

GATE has tested all three. For the dynamic-array problem the aggregate method is the cleanest, but the accounting method is the most intuitive — each append "pre-pays" a little for its share of a future resize.

Worst case versus amortized

A single append in the worst case is O(n) — exactly when the resize triggers. Amortized cost is O(1) because the expensive operations are rare and their cost is spread over the many cheap operations they enable.

In a hard real-time system, you may care about the worst-case latency of a single operation, not the average. For such systems, a different data structure (linked list, or a deamortized variant) may be preferred. But for almost every general-purpose application, amortized O(1) is exactly what you want — and explains why ArrayList in Java or vector in C++ feel "constant time" even though they are doing periodic batch reorganisations.

Worked example

Question: Starting from a dynamic array with capacity 1, perform 17 appends. Compute the total copy work using the doubling strategy.

Solution:
Step 1: Resizes happen when the array is full. With initial capacity 1, resizes occur at sizes 1, 2, 4, 8, 16. Copy work at each resize: 1, 2, 4, 8, 16 elements.
Step 2: Total copy work = 1 + 2 + 4 + 8 + 16 = 31.
Step 3: Cheap append work = 17 (one slot-write per append).
Conclusion: Total = 31 + 17 = 48 unit operations for 17 appends, or about 2.8 per append. As n grows, this constant tightens toward 3 — confirming the O(1) amortized bound.

Real-world example

Real-world example: Pinterest, Flipkart, and most large Indian e-commerce backends store user-session event logs in dynamically resizable buffers before flushing them to a database. A user might trigger a few events or a few thousand in a single session. The dynamic array gives O(1) amortized append for the common case, and the rare resize copy is invisible because it is amortized over millions of cheap appends. Without geometric growth, the server would spend quadratic time per session — unacceptable at scale.

Common misconception

Common misconception: "Amortized cost is the same as average-case cost." Wrong. Average-case cost depends on a probability distribution over inputs — for example, the average lookup time in a hash table assuming uniformly distributed keys. Amortized cost is a worst-case guarantee on a sequence: no matter how the adversary orders n appends, the total cost is O(n). It is a deterministic bound, not a statistical average.

Reversing an array sounds trivial — and yet it is the operation behind rotation, palindrome checking, and several classic GATE PYQ questions. Getting the loop bound and index arithmetic right is the difference between a clean O(n) solution and a subtle bug.

Definition: An in-place algorithm modifies its input directly using only a small, constant amount of extra memory (O(1) auxiliary space), rather than constructing a new copy of the data.

Definition: An array reversal is the operation that rearranges the elements of an array so that the element originally at index i ends up at index n − 1 − i, where n is the array's length.

The Two-Pointer Idea

The clean way to reverse an array in place is the two-pointer technique:

1. Place pointer i at the start (index 0).
2. Place pointer j at the end (index n − 1).
3. Swap A[i] with A[j].
4. Move i forward, move j backward.
5. Stop when i ≥ j.

A loop-based version using a single index expresses the same idea:

for i = 0 to n/2 - 1:
    swap(A[i], A[n - 1 - i])

The expression n − 1 − i is the mirror image of index i about the centre of the array. Swapping each i with its mirror, only over the first half, reverses the array. The middle element (when n is odd) maps to itself — no swap needed.

Why n/2 — Not n

The most common bug is writing for i = 0 to n - 1. This swaps each pair twice: once when i is on the left of the pair, and once when i is on the right. Two swaps cancel out — and the array returns to its original state. Always use n/2 as the upper bound (use integer division).

Complexity Analysis

• Time complexity: O(n). The loop runs n/2 times, each iteration performs one swap (three constant-time operations). The total is c × n/2, which is Θ(n).
• Space complexity: O(1). Only one temporary variable is needed for the swap (or none if using (a, b) = (b, a) tuple-assignment in Python). No new array is allocated.

This makes reversal the gold standard of in-place operations — minimal memory, optimal time.

Building Block for Rotation

Reversal becomes the elegant primitive for array rotation. To rotate an array of length n by k positions to the left:

1. Reverse the first k elements: A[0..k−1].
2. Reverse the remaining n − k elements: A[k..n−1].
3. Reverse the entire array A[0..n−1].

Result: A is rotated left by k. Why does this work? Each of the three reversals is its own inverse; the composition of the three reversals equals a cyclic left-shift by k. Total cost: three O(n) reversals = still O(n) time, O(1) extra space. This is the famous "reversal algorithm" that GATE has tested at least twice as a one-mark MCQ.

For right rotation by k, simply reverse-rotate by n − k (or apply the same three reversals in opposite order).

Why it matters: GATE CSE Data Structures section regularly tests array manipulation under tight complexity bounds. Knowing both the in-place trick and the rotation-by-reversal idea covers a large slice of probable questions.

Real-world example: WhatsApp message bubbles displayed bottom-up are conceptually the reverse of the chronological log. Internally, a fixed-size buffer is reversed in place to keep memory usage flat — exactly the pattern this lesson teaches.

Common misconception: "Reversing an array of size n takes n swaps." Wrong. It takes exactly ⌊n/2⌋ swaps. For n = 6, that is 3 swaps: (0,5), (1,4), (2,3). For n = 7, also 3 swaps: (0,6), (1,5), (2,4); the middle element (index 3) stays put.

Question: An array A of size n = 5 holds [10, 20, 30, 40, 50]. Show each step of the in-place reversal.
Solution:
Step 1: i = 0, j = 4. Swap A[0] and A[4]. Array becomes [50, 20, 30, 40, 10].
Step 2: i = 1, j = 3. Swap A[1] and A[3]. Array becomes [50, 40, 30, 20, 10].
Step 3: i = 2, j = 2. They meet; stop. Index 2 (the middle) is unchanged.
Conclusion: After 2 swaps the array is reversed. The loop runs ⌊5/2⌋ = 2 times.

Question: An array of 10 elements is rotated left by 3 using the reversal algorithm. How many element-swaps occur in total?
Solution:
Step 1: Reverse first 3 elements → ⌊3/2⌋ = 1 swap.
Step 2: Reverse remaining 7 elements → ⌊7/2⌋ = 3 swaps.
Step 3: Reverse all 10 elements → ⌊10/2⌋ = 5 swaps.
Conclusion: Total swaps = 1 + 3 + 5 = 9. Still O(n), as 9 ≤ 3n/2.

A GATE Twist

If a question asks for the value of the loop counter when the loop terminates in C-style:

for (i = 0; i < n/2; i++)
    swap(A[i], A[n-1-i]);

After execution, i = n/2 (with integer division). For n = 5, i = 2. For n = 6, i = 3. This is a favourite micro-question for GATE PYQ MCQs.

Cover the answer, recall, then check. 12 cards on array operation complexities.

Q1. Time to access A[i] by index?
A1. O(1) — random access via address arithmetic.

Q2. Time to search for a value in an UNSORTED array?
A2. O(n) worst/average (linear search).

Q3. Time to search in a SORTED array using binary search?
A3. O(log n).

Q4. Insert at the END of an array (space available)?
A4. O(1).

Q5. Insert at the BEGINNING of a filled array?
A5. O(n) — every existing element shifts right by one.

Q6. Insert at arbitrary position i (0-based) in an array of n elements?
A6. O(n) worst; exactly n − i elements shift.

Q7. Delete from the beginning of an array?
A7. O(n) — shift all remaining elements left.

Q8. Delete from the end of an array?
A8. O(1).

Q9. Dynamic array (vector / ArrayList) growth strategy and append cost?
A9. Capacity doubles on overflow; append is amortized O(1), worst-case single append O(n) during resize.

Q10. Total cost of n appends to a doubling dynamic array?
A10. O(n) total (amortized O(1) each) — resize copies sum to < 2n.

Q11. Main advantage of arrays over linked lists?
A11. O(1) random access and cache locality (contiguous memory).

Q12. Main disadvantages of a (static) array?
A12. Fixed capacity and O(n) insert/delete in the middle due to shifting.

Key formulas

• Access by index: O(1); update by index: O(1).
• Search (unsorted): O(n); search (sorted, binary search): O(log n).
• Insert/delete at end (dynamic array, amortised): O(1); at arbitrary position: O(n) due to shifting.
• Address of A[i] (1-D, base B, size w, lower bound L): B + (i − L)·w.
• 2-D row-major A[i][j]: B + ((i − L_r)·C + (j − L_c))·w, C = number of columns.
• 2-D column-major: B + ((j − L_c)·R + (i − L_r))·w, R = number of rows.
• Dynamic array doubling gives amortised O(1) append over n inserts (Σ ≤ 2n copies).

Usage: address-calculation MCQs just plug into the row-major or column-major formula.