Array Time & Space Complexity

The Complete Array Operation Complexity Table

This is the definitive reference for every fundamental array operation. The reasons behind each complexity are explained in the sections below.

Why Access Is O(1)

Array elements are stored in a contiguous block of memory. The address of any element is computed directly:

address of arr[i] = base_address + (i × element_size)

This is one multiplication and one addition — a fixed number of steps regardless of array size or index position. Whether you access the first element or the millionth, exactly the same computation happens.

This is the only data structure where access by position is O(1). Linked lists are O(n) — you must follow pointers from the head. Trees are O(log n) — you must traverse from the root. Arrays are unique because memory is directly addressable by offset.

Why Insert and Delete Are O(n)

Because array elements must stay contiguous in memory, inserting or deleting anywhere except the end requires shifting elements to fill or create space.

Delete at index 2 in [A, B, C, D, E]:

Before:  [A, B, C, D, E]
                 ↑ delete here

Shift left from index 3 onward:
  arr[2] ← arr[3]  → [A, B, D, D, E]
  arr[3] ← arr[4]  → [A, B, D, E, E]

After:   [A, B, D, E]

Elements shifted: n - k - 1
When k = 0 (delete first): shift n-1 elements → O(n)
When k = n-1 (delete last): shift 0 elements → O(1)

The number of shifts is n - k - 1 for deletion and n - k for insertion. In the worst case (k = 0), all n elements shift. In the best case (k = n - 1), zero elements shift. Big-O measures the worst case — so insert and delete are O(n).

Amortized O(1) for Dynamic Array Append

Dynamic arrays (ArrayList, Python list, C++ vector, JavaScript array) appear to append in O(1), but occasionally trigger a resize — copying all elements to a larger block — which costs O(n).

How can the overall cost still be O(1)?

Python list resizes at: 0, 4, 8, 16, 32, 64, 128, ...  (roughly doubles)

Insertions 1-4:   no resize    → 4 cheap operations
Insertion  5:     resize (copy 4 elements) + insert
Insertions 6-8:   no resize    → 3 cheap operations
Insertion  9:     resize (copy 8 elements) + insert
Insertions 10-16: no resize    → 7 cheap operations
Insertion 17:     resize (copy 16 elements) + insert

Total work for n insertions:
  Insertions themselves:  n operations
  All resize copies:      1 + 2 + 4 + 8 + ... + n/2 ≈ n operations (geometric sum)

Total: 2n operations for n insertions
Amortized per insertion: 2n / n = 2 = O(1)

Each individual resize is O(n), but resizes happen exponentially less frequently as the array grows. Spread across all insertions, the cost per operation averages to O(1). This is amortized O(1) — the total work divided by the number of operations.

Output (approximate — varies by machine):
Appended 1,000,000 elements
Final size: 1000000
Total time: ~15-50 ms

Algorithm Complexity on Arrays

Beyond the basic operations, every algorithm applied to an array has its own complexity. This is the reference for the most common algorithms.

Space Complexity of Common Array Patterns

Space complexity in array problems depends on whether you create auxiliary data structures.

O(1) Auxiliary Space — In-Place

Operations that modify the existing array without allocating new memory.

• ›Reverse in-place: two pointer variables and one temp → O(1)
• ›Rotate in-place: three pointer variables → O(1)
• ›Swap two elements: one temp variable → O(1)
• ›Two-pointer scan (palindrome, pair sum): two index variables → O(1)
• ›Kadane's algorithm (maximum subarray): two running variables → O(1)

Output:
Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Max subarray sum: 6

O(n) Auxiliary Space — New Arrays or Hash Structures

Patterns that create new data structures proportional to input size.

• ›Prefix sum array: new int array of size n → O(n)
• ›Hash map for frequency or lookup: up to n entries → O(n)
• ›Copying array: new allocation of size n → O(n)
• ›Merge sort merge step: auxiliary array of size n → O(n)

Output:
Sum [2..5]: 15
Sum [0..7]: 31
Pairs summing to 5: 2

Brute Force vs Optimized: Complexity Comparison

The difference between acceptable and unacceptable solutions is almost always the complexity of the inner operation. This table shows the most common array problems with their brute force and optimized complexities.

The pattern is consistent: a brute force inner loop searching or comparing across the array is O(n) per outer iteration = O(n²) total. The optimization is either precomputing a lookup structure (hash map → O(1) lookup) or maintaining a running invariant (sliding window, Kadane's → O(1) per step).

Reading Constraints to Predict Required Complexity

In interview problems, the constraint on n is not decoration — it is a hint about what complexity is expected. This is how experienced engineers read constraints.

n ≤ 10:
  Any complexity works including O(n!)
  Brute force backtracking is fine.

n ≤ 100:
  O(n²) or O(n³) is acceptable.
  Nested loops fine.

n ≤ 1,000:
  O(n²) still fine (~1 million operations).
  Bubble sort, selection sort acceptable.

n ≤ 100,000 (10^5):
  O(n²) is too slow (~10 billion operations).
  Need O(n log n) or O(n).
  Sorting-based or hash-based solutions required.

n ≤ 1,000,000 (10^6):
  O(n log n) is borderline (~20 million operations).
  O(n) strongly preferred.
  Hash map, prefix sum, sliding window, Kadane's.

n ≤ 10^9:
  O(n) is too slow.
  Need O(log n) or O(1).
  Binary search on sorted/answer space.

Applying This in Practice

When you read a constraint, immediately ask: given this n, what is the maximum complexity my solution can have?

Problem: "Given n integers (n ≤ 10^5), find all pairs with sum = target."

Constraint: n = 100,000
Max acceptable complexity: O(n log n) or O(n)

Brute force: O(n²) → 10^10 operations → too slow
Sorting + two pointers: O(n log n) → acceptable
Hash map: O(n) → optimal

The Space-Time Tradeoff in Arrays

Every array optimization involves trading memory for speed. The three most common tradeoffs:

Tradeoff 1 — Hash Map for Lookup

Store elements as you scan to avoid re-scanning:

Brute force: scan array for each element  → O(n²) time, O(1) space
Optimized:   hash map for O(1) lookup     → O(n)  time, O(n) space

Cost: O(n) extra space
Gain: O(n²) → O(n) time

Tradeoff 2 — Prefix Array for Range Queries

Precompute cumulative sums to answer range queries instantly:

Without prefix: recompute range sum each time → O(n) per query
With prefix:    build once, query in O(1)      → O(1) per query after O(n) build

Cost: O(n) extra space for prefix array
Gain: O(n) → O(1) per range query

Tradeoff 3 — Copy for Safety

Copy an array before modifying when the original must be preserved:

In-place modification: O(1) extra space, original is lost
Copy then modify:      O(n) extra space, original preserved

Cost: O(n) space
Gain: original data preserved for further use

Understanding these tradeoffs lets you state them explicitly in interviews — a sign that your reasoning is engineering-grade, not just academic.

Worst Case, Best Case, and Average Case for Array Algorithms

Not all complexities are equal across all inputs. For array algorithms specifically:

Quick Sort's worst case (O(n²)) occurs when the pivot is always the smallest or largest element — typically on already-sorted input. This is why production implementations use randomized pivots or the median-of-three rule.

Hash map lookup is O(n) in the absolute worst case (all keys hash to the same bucket), but this is essentially impossible with a good hash function on random data.

Practical Complexity Checklist for Array Problems

Before finalizing any array solution, run through this checklist:

Step 1: What is n?
  → Read the constraint. Determine max acceptable complexity.

Step 2: How many loops touch the array?
  One loop:          O(n)    time
  Two sequential:    O(n)    time  (add, don't multiply)
  Two nested:        O(n²)   time  (multiply)
  Loop + binary:     O(n log n) time

Step 3: What auxiliary structures are created?
  No new arrays/maps:         O(1) space
  One array of size n:        O(n) space
  One array of size k < n:    O(k) space
  Two arrays of size n:       O(n) space (constants drop)
  2D array of size n×n:       O(n²) space

Step 4: Is the space tradeoff justified?
  O(n) space for O(n²) → O(n) time: almost always yes
  O(n) space for O(n) → O(1) time: depends on query count

Step 5: Are there hidden O(n) operations inside loops?
  Common traps:
  - list.contains(x) inside a loop → O(n²) total → use a set
  - arr.indexOf(x) inside a loop   → O(n²) total → use a map
  - arr.remove(x) inside a loop    → O(n²) total → mark and sweep

Interview Questions

Q: What is amortized O(1) and how does it apply to dynamic arrays?

Amortized O(1) means the average cost per operation over a sequence of operations is O(1), even if individual operations are occasionally expensive. Dynamic arrays double their capacity when full, copying all elements — an O(n) operation. But because doubling happens exponentially less often as the array grows, the total work across n appends is O(n), giving O(1) per append on average. Single worst-case appends are O(n), but you cannot trigger them repeatedly.

Q: Why is binary search O(log n) while linear search is O(n)?

Binary search eliminates half the remaining elements at each step. Starting with n elements, after one step you have n/2, then n/4, then n/8. The number of steps to reach 1 element is log₂(n). Linear search eliminates only one element per step — taking up to n steps. Binary search requires a sorted array because the comparison at each midpoint must meaningfully tell you which half contains the target.

Q: Why does merge sort use O(n) space while quick sort uses O(log n)?

Merge sort needs an auxiliary array of size n to hold merged results during the merge step. It cannot merge two subarrays in-place efficiently. Quick sort partitions in-place — no auxiliary array — but uses O(log n) space for the recursion stack (the depth of recursive calls on average, since each call halves the problem). In the worst case quick sort's stack is O(n).

Q: If two sequential loops both touch all n elements, is the time complexity O(n) or O(2n)?

O(n). Sequential loops add their complexities: O(n) + O(n) = O(2n). Constants are dropped in Big-O analysis, giving O(n). Two sequential O(n) loops are still O(n) — not O(n²). Only nested loops multiply.

FAQs

Does the complexity of accessing an element change if the array is sorted?

No. Sorted or not, arr[i] is O(1) because index access uses the address formula directly. Sorting affects search complexity (enabling binary search at O(log n) instead of O(n)) but never affects access-by-index complexity, which is purely a memory address computation.

Is creating a copy of an array O(n) time or O(1)?

O(n) time and O(n) space. Every element must be read from the original and written to the new allocation — n reads and n writes. Arrays.copyOf in Java, slicing in Python (arr[:]), and spread in JavaScript ([...arr]) are all O(n). There is no shortcut — you cannot copy n values without touching each one.

Why is the worst-case complexity of hash map lookup O(n) if hash maps are supposedly fast?

Hash maps use a hash function to map keys to buckets. If many keys hash to the same bucket (a collision), they form a linked list or tree in that bucket. In the absolute worst case, all n keys go into the same bucket, making every lookup O(n). In practice with a good hash function this is astronomically unlikely, which is why the average case is O(1). Production hash maps use techniques like load factors, rehashing, and collision-resistant hash functions to ensure practical O(1) performance.

Does sorting an array before solving a problem always improve complexity?

No — sorting costs O(n log n), which is worse than O(n). If the problem can be solved in O(n) without sorting (using a hash map, prefix sum, or single-pass scan), sorting is counterproductive. Sorting helps when it enables O(log n) binary search or O(n) two-pointer techniques that would otherwise require O(n²) brute force — in those cases the O(n log n) sort cost is justified.

Quick Quiz

Question 1: An algorithm has one loop over n elements, and inside the loop it calls list.contains(x) which is O(n). What is the overall time complexity?

• ›A) O(n)
• ›B) O(n log n)
• ›C) O(n²)
• ›D) O(2n)

Answer: C) O(n²). The outer loop runs n times. Each iteration calls contains() which is O(n). Nested operations multiply: O(n) × O(n) = O(n²). This is the classic hidden-loop trap — replacing contains() with a set lookup (O(1)) reduces the total to O(n).

Question 2: A problem has n ≤ 10^6. Your solution uses two sequential loops, each O(n), and a hash map of size n. What is the time and space complexity?

• ›A) O(n²) time, O(n) space
• ›B) O(n) time, O(n) space
• ›C) O(2n) time, O(n) space — different from O(n)
• ›D) O(n log n) time, O(n) space

Answer: B) O(n) time, O(n) space. Two sequential loops add: O(n) + O(n) = O(2n) = O(n). The hash map is O(n) space. Both are acceptable for n ≤ 10^6.

Question 3: You append elements one at a time to a dynamic array using a doubling strategy. After n appends, what is the total time spent on resize operations?

• ›A) O(n²) — each resize copies more elements
• ›B) O(n) — geometric series sums to 2n
• ›C) O(n log n) — log n resizes of increasing size
• ›D) O(1) — resizes are negligible

Answer: B) O(n) — geometric series sums to 2n. Resize sizes are 1, 2, 4, 8, ..., n/2. Their sum = 1 + 2 + 4 + ... + n/2 = n - 1 ≈ O(n). Total work for n appends including all resizes is O(n), giving O(1) amortized per append.

Question 4: Which sorting algorithm has O(1) auxiliary space and O(n log n) average time?

• ›A) Merge Sort — O(n log n) time, O(n) space
• ›B) Bubble Sort — O(n²) time, O(1) space
• ›C) Quick Sort — O(n log n) average time, O(log n) stack space
• ›D) Insertion Sort — O(n²) average time, O(1) space

Answer: C) Quick Sort. Quick Sort partitions in-place using O(1) auxiliary array space. Its recursion stack uses O(log n) space on average (O(n) worst case). Average time is O(n log n). Merge Sort's merge step requires O(n) extra array space. Bubble and Insertion Sort are O(n²).

Summary

Array complexity is determined by two physical constraints: contiguous memory enables O(1) index access, and maintaining contiguity forces O(n) shifting for mid-array insert and delete.

The key complexities to carry as permanent intuition:

• ›Access and update by index → always O(1), no exceptions
• ›Insert and delete at end → O(1) amortized for dynamic arrays
• ›Insert and delete at middle or beginning → O(n) because of shifting
• ›Traversal of n elements → O(n) minimum — cannot skip elements
• ›Binary search → O(log n) on sorted arrays
• ›Sorting → O(n log n) optimal for comparison-based sorts
• ›Hash map for lookup → O(n) space buys O(1) per lookup
• ›Prefix array → O(n) space buys O(1) per range query

Read constraints before choosing an algorithm. n ≤ 10³ tolerates O(n²). n ≤ 10⁵ requires O(n log n) or better. n ≤ 10⁶ requires O(n). n ≤ 10⁹ requires O(log n) or O(1). The constraint tells you what complexity is acceptable — your job is to find a solution that fits within it.

In the next topic, you will explore 2D Arrays — extending these concepts to two-dimensional grids, matrix traversal, and the complexity of row-major vs column-major access patterns.