Core Concept Mastery • DSA Module
Arrays excel at reading (O(1)) but struggle with inserting or deleting in the middle (O(n)) because elements must shift to make or fill space. Search in an unsorted array is O(n) because you must check every element.
The Cinema Seat Problem: You and 4 friends sit in a row. A new friend arrives and wants to sit in the middle. Everyone to the right has to scoot over one seat. That shifting is O(n) — the same pain arrays feel when you insert in the middle.
Select a mode to start
Click Insert at index 1 or 2 and watch the elements shift.
1// Insert 'x' at index 'pos'2// Everyone from pos onward must move right3for (int i = n; i > pos; i--) {4arr[i] = arr[i-1]; // scoot right5}6arr[pos] = x; // finally place x7// Time: O(n) — up to n elements shift
| Action | Speed | Analogy |
|---|---|---|
| Access | O(1) | Teleport to address |
| Search | O(n) | Knock every door |
| Insert (middle) | O(n) | Cinema seat scoot |
| Delete (middle) | O(n) | Fill the gap |
Let's break down each operation.
Access (Read) — O(1)
You already know this. Give an index, get the value. The formula gets you there instantly. Netflix jumping to minute 55:00? Same idea.
Search (Find a value) — O(n)
If the array is unsorted, you have no choice: check index 0, then 1, then 2... until you find it or run out. Average case: ~n/2 checks. Worst case: n checks. So we say O(n).
Insert (at position) — O(n)
To insert at index 2, you must shift everything from index 2 onward one slot to the right. That's potentially n elements moving. The only cheap insert is at the end of a dynamic array — O(1) amortized (no shifting).
Delete (at position) — O(n)
Same story. Remove index 2? Everything after it must shift left to fill the gap. Up to n-1 elements move. O(n).
The Report Card
When you choose a data structure, you trade off these operations. Need fast lookups by index? Use an array. Need frequent insertions in the middle? Consider a linked list. Understanding the cost of each operation helps you pick the right tool.
"What is the best place to insert in an array if you want to avoid shifting?"
At the end — no elements need to move. O(1) for dynamic arrays.