4 ms·

“(although, for many methods, it can still be bounded by amortized O(1) time)” I don’t follow this. Does it mean that you can build the perfect hash table in c

• 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 ago
    tl;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).
• martincmartin 9y ago
  "Amortized O(1) time" means the time for n operations is O(n), even though individual operations might be more than O(1). Building the hash table means adding n things. So they're saying its linear.