8 ms·

I am curious, what other name does it go by? I had a strong response because this came up while arguing about the cost of appending to a vector in loop. He had

• jedberg 5y ago
  Honestly, I've never heard a term for it. Just talked about in the abstract: "That operation is O(n log n)" "Sure, but that operation doesn't happen on every loop, the entire algorithm is still O(n)".
  • pitched 5y ago
    It reminds me a bit more of talking about p50 vs p99 latency times but where we’re not measuring production data, more like what we’re guessing production loads will look like.
  • not2b 5y ago
    I'm old enough to remember that Microsoft got this wrong back in the early 90s. In early versions of Microsoft Foundation Classes, which Windows C++ programmers were using before the STL took over and std::string became the thing, repeatedly appending a character to a string (I think it was CString) was quadratic, because they didn't increase array size by a multiplicative factor, but by a linear amount, so you'd get a ton of reallocation and copying. I used to use versions of this as an interview question. However, language for concepts evolves with time, and younger programmers shouldn't assume that older programmers don't know a concept because they learned it by a different name. (Though they might not know the concept).
    • Chris_Newton 5y ago
      In early versions of Microsoft Foundation Classes … repeatedly appending a character to a string (I think it was CString) was quadratic, because they didn't increase array size by a multiplicative factor, but by a linear amount, so you'd get a ton of reallocation and copying. I remember seeing production code slow to a crawl once because of that one. It wasn’t long after I’d left university, where I’d studied CS but the lectures on complexity theory had seemed quite theoretical at the time. Suddenly, here was a vivid example of how it could cause a problem in practice, in a situation as everyday as putting some text in a UI. The solution — using a string builder — then led me to several other principles about choosing an efficient internal representation for data and it being OK not to convert that data into its “true” form until you’re ready to use it. I suppose I should thank whoever made the original mistake, because despite causing a frustrating afternoon with a profiler, it also created several lightbulb moments early in my career.
• tomc1985 5y ago
  You likely have lots of colleagues that never completed a CS degree.
• bigiain 5y ago
  Knowing the generally used names of things isn't the same as knowing the things. "All science is either physics or stamp collecting." -- Ernest Rutherford. I suspect there are many people who understand the Big-O, Omega, Theta, and Little-O implications (the physics) but might not have heard the term "constant time amortized" (the stamp collecting). (Not that knowing accepted names is bad, it's much much easier to communicate when everyone shares a set of terms that they agree on the meaning of...)
  • blacktriangle 5y ago
    Had another great quote from a professor: every introductory course is fundamentally a language course.
• cshepher 5y ago
  I have an MS in Computer Science (from the mid-90's) and have never heard of this term. (it seems simple enough once you read the definition of it). My graduate level algorithms class used average or probabilistic cost, but never the term amortized.
• 0xEFF 5y ago
  What’s the difference between “constant time” and “constant time amortized?”
  • hansvm 5y ago
    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).
    • StandardFuture 5y ago
      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.
  • sobani 5y ago
    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).
• hibbelig 5y ago
  Just a data point: I could guess what you meant by “constant time amortized” but I’ve never heard of “amortized analysis”. I’ve learned the same concepts under “big O notation” or just “complexity”. I suggest that you consider whether it’s possible that other people know the same concept under a different name and don’t write them off as quickly if they don’t know your favorite term.
• CRConrad 5y ago
  Amortize is what you do with the loan on your home; never heard that particular word in this context. I am surprised at how blithely you assume the terminology you learned at your particular college is universal, and how parochially you seem to look down on people just because they don't share that particular terminology.