1.5Operation cost cheat-sheet
The idea
Different structures trade search, insert and delete costs. Knowing the table by heart answers many "which structure?" questions.
Think of it like this: Choosing between a filing cabinet, a stack of papers and an index: each is fast at something and slow at another.
Why it exists
GATE often asks which structure gives the best worst-case for a given mix of operations.
How it works
- List the operations the problem needs.
- Look up each cost in the table.
- Compare worst case against expected case.
- Check whether ordering (sorted output, min) is needed.
Worked example: Need insert, delete and find-min
A binary heap: O(log n) insert, O(log n) delete-min, O(1) find-min. A sorted array makes insert O(n).
Now play with it
- →Scan the table for the row that has O(log n) for all three.
- →Note that the hash table is expected O(1) but loses ordering.
| Structure | Search | Insert | Delete | Find min |
|---|---|---|---|---|
| Unsorted array | O(n) | O(1) at the end | O(n) | O(n) |
| Sorted array | O(log n) | O(n) | O(n) | O(1) |
| Linked list | O(n) | O(1) at the head | O(n) | O(n) |
| Binary search tree (worst) | O(n) | O(n) | O(n) | O(n) |
| Balanced BST (AVL) | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash table (expected) | O(1) | O(1) | O(1) | O(n) |
| Binary min-heap | O(n) | O(log n) | O(log n) (min) | O(1) |
Worst case unless marked expected. "Insert" assumes you do not need to keep an array sorted unless stated.
Check yourself
Which structure gives O(log n) worst-case search, insert and delete?
Exam notes (the dense version)
Know the worst-case cost of search, insert and delete for each structure: unsorted array O(n)/O(1)/O(n), sorted array O(log n)/O(n)/O(n), linked list O(n)/O(1)/O(n), BST O(h), balanced BST O(log n), hash table O(1) expected, binary heap O(n) search, O(log n) insert and delete-min, O(1) find-min.
Previous year questions: Arrays, Stacks, Queues & Linked Lists (14)
PYQs are grouped by topic, so this is the full set for Arrays, Stacks, Queues & Linked Lists; try the ones that match this subtopic. Open all 14 on the topic page.