Static Arrays

What is a static array?

A static array is a fixed-size collection of elements stored in contiguous memory.

Index:    0    1    2    3    4
          ↓    ↓    ↓    ↓    ↓
        ┌────┬────┬────┬────┬────┐
Memory: │ 10 │ 20 │ 30 │ 40 │ 50 │
        └────┴────┴────┴────┴────┘

Important properties:

• Fixed size
• Contiguous memory
• O(1) index access
• Insertion/deletion may require shifting

Index access

Because elements are contiguous:

address = base_address + index × element_size

Therefore:

arr[i]

→ O(1)

Updating an existing element is also O(1):

arr[2] = 100

Searching

Searching an unsorted array may require inspecting every element:

Search → O(n) worst case

Insertion

Insert 25 at index 2:

[10, 20, 30, 40]
          ↓
[10, 20, 25, 30, 40]

Elements after the insertion point must shift.

Therefore:

Insert beginning → O(n)
Insert middle    → O(n)
Insert end       → O(1)*

* Assuming capacity is already available.

Deletion

Deleting from the middle also requires shifting:

[10, 20, 30, 40, 50]
          ↓
[10, 20, 40, 50]

Therefore:

Delete beginning → O(n)
Delete middle    → O(n)
Delete end       → O(1)

Operation table

Operation	Complexity
Access arr[i]	O(1)
Update arr[i]	O(1)
Search	O(n)
Insert beginning	O(n)
Insert middle	O(n)
Insert end*	O(1)
Delete beginning	O(n)
Delete middle	O(n)
Delete end	O(1)

Important interview trick: Does order matter?

Suppose:

[10, 20, 30, 40, 50]

Delete 20.

If order matters

[10, 30, 40, 50]

Elements shift → O(n).

If order does NOT matter

Replace 20 with the last element:

[10, 50, 30, 40]

Then remove the last element.

→ O(1)

This is a useful interview optimization.

Static vs dynamic arrays

A static array has fixed capacity.

A dynamic array can grow when it runs out of capacity.

Python’s list is a dynamic array, not a traditional fixed-size static array.

Mental model

Array
  ↓
Contiguous memory
  ↓
Direct index calculation
  ↓
Access = O(1)

Insertion/deletion
  ↓
May require shifting
  ↓
O(n)

Interview takeaway

“Indexed access is O(1) because the array is contiguous and the address can be calculated directly. Insertion or deletion from the beginning or middle is O(n) because subsequent elements may need to be shifted.”

Quick revision

Static Array:
- Fixed size
- Contiguous memory
- Access → O(1)
- Update → O(1)
- Search → O(n)
- Insert beginning/middle → O(n)
- Delete beginning/middle → O(n)
- Insert/delete end → O(1), when capacity is available

Key question:
Does the operation require shifting elements?

If yes → potentially O(n)
If no → often O(1)