3 ms·
Inserting into a non-static hash table is measured per-element so the blog is also saying O(1) per element, which is linear time.
by aidenn0 9y ago
Inserting into a non-static hash table is measured per-element so the blog is also saying O(1) per element, which is linear time.
- martincmartin 9y agotl;dr: Each insertion is O(n), but n insertions are also O(n). Saying "amortized time is O(1)" just means the time for n operations is O(n). To be pedantic: some individual insertions can take more the O(1), namely when you have to rehash it can take O(n) time. So the tight upper bound on each insertion is O(n). So doing n of them seems like it might take O(n^2). Except you can't rehash on every insertion. So even though the time to insert one is O(n), the time to insert n is also O(n). If you amortize that time over all n insertions, you get O(n) / n == O(1).