News for hackers. Stuff that matters.
Re:An incomplete list of skills senior engineers need, beyon... by 0xEFF on Monday June 07, 2021 @01:56AM (#27419449)
What’s the difference between “constant time” and “constant time amortized?”
Re:An incomplete list of skills senior engineers need, beyon... by hansvm on Monday June 07, 2021 @02:50AM (#27419772)
Replace "amortized" with "on average" and you'll have the basic concept.

A constant time operation has bounded runtime for every input, but an amortized constant time operation can allow for much longer runtimes so long as they happen sufficiently rarely. Concretely, doing an amortized constant time operation N times should be O(N).

Re:An incomplete list of skills senior engineers need, beyon... by StandardFuture on Monday June 07, 2021 @07:46PM (#27428834)
It sounds like "amortized" is close to mathematically meaningless in that case.

Why not use actual statistics jargon at that point?

Sometimes we need to realize that the reactions of people inside of the software community are almost purely due to their own personal (usually social) insecurities and are not worth addressing.

We have an entire thread giving credibility to someone who absolutely idiotically dismissed another person for not knowing the meaning of a single word.

The person who was temporarily ignorant of the meaning of that word is not the one I am thinking needs to be ignored here.

Re:An incomplete list of skills senior engineers need, beyon... by sobani on Monday June 07, 2021 @04:10AM (#27420233)
To expand on @hansvm answer, an example would be a hash table.

Insertion is O(1) (constant time), most of the time.

But once in a while the collection will need to increase the size of the underlying array, which causes the entire table to be reorganized. That specific insertion will then be O(N) (where N is the size of table). The good news is that this reorganization happens only once every N insertions.

So amortized insertion is O(1), even if in the worst case it can be O(N). Depending on your use case you can hand wave the worst case away with "amortized it's constant time", or you can choose a tree instead, for a more predictable O(log N), or you could use some other mitigating tactic, like initializing your hash table with enough storage _for all use cases_ so you can guarantee O(1).