complexity
-
0Why is a hash table lookup called O(1) when collisions exist?Every source says hash table lookup is O(1), then the next paragraph admits that collisions make it O(n) in the worst case. Both cannot be the headline figure. If the worst case really is linear, why is O(1) the number…4 OpenCS Algorithms Circle · 8h ago
-
0If mergesort is O(n log n) always, why is quicksort usually faster?On paper mergesort looks strictly better. It is O(n log n) in every case, while quicksort degrades to O(n²) if the pivots go badly. Yet almost every standard library sort is quicksort or a hybrid built on it. What is…3 OpenCS Algorithms Circle · 8h ago
-
0Why is binary search O(log n) and not O(n/2)?Binary search halves the list each time, so my first instinct was that it does about n/2 work. I know the answer is log n but I cannot see where the logarithm comes from, and halving once really does remove half the…3 OpenCS Algorithms Circle · 8h ago