Data Structures
Don't do this
3 data structure mistakes that cost exam marks
3 mistakes that cost marks in data structures
Quick check · tap an answer to continue
Lesson notes
Key points
- Array insert is O(1): Inserting in an array's middle shifts elements, so it is O(n), not O(1).
- Linked list access O(1): Reaching the k-th node means walking from the head, so linked list access is O(n).
- All BST search is O(log n): An unbalanced BST can become a line, giving O(n) search; only balanced trees guarantee O(log n).
Takeaway: Name the case: average, worst, balanced or not.
Quick check: What is the worst-case search time in an unbalanced binary search tree?
- O(1)
- O(log n)
- O(n)
A skewed tree behaves like a linked list, so search is O(n).
Lessons like this, for your syllabus.
Short narrated study videos written for your course, level and exam. Free to start.
Get lessons for your own syllabus