Algorithms and Data Structures · Middle · Question 73 of 75
What does it cost to insert a value into a sorted array and keep it sorted?
- ✓Correct answer: O(n): finding the spot is O(log n), but shifting elements is O(n)
- 2O(1): JavaScript arrays can insert anywhere for free
- 3O(log n): binary search finds the position directly
Explanation
Binary search finds the position quickly, but splice still moves every later element. For many inserts with lookups in between, a balanced tree or a heap (depending on the queries) is a better fit.