5 ms·
"fixed it with an algorithmic change, reducing backup times exponentially" If the backup times were O(n^2), are they now O(n^2 / 2^n)? I would guess not.
by hiddew 1y ago
"fixed it with an algorithmic change, reducing backup times exponentially"
If the backup times were O(n^2), are they now O(n^2 / 2^n)? I would guess not.
- School-Cotton 1y agoThis is not the precise mathematical definition of exponential, but rather the colloquial one, where it just means "a lot".
- cvoss 1y agoYou shouldn't use a word that can carry a precise mathematical meaning in a sentence that literally uses mathematical notation in order to speak precisely and then expect readers not to interpret the word in the precise mathematical way.
- blharr 1y agoI somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch
- School-Cotton 1y ago“Dramatically” ?
- deleted 1y ago[deleted]
- remram 1y ago"a lot"
- jjmarr 1y ago"by a factor of `n`" also sounds impressive.
- deleted 1y ago[deleted]
- jrochkind1 1y agoIf you just mean "a lot" in a non-technical sense, there are plenty of words available. enormously. immensely. tremendously. remarkably. incredibly. vastly.
- bobbylarrybobby 1y ago“From quadratic to linear” seems fine.
- bobbylarrybobby 1y ago“From quadratic to linear” or “... to constant” seems fine.
- morepedantic 1y agoAlgorithmic? Big-O? Polynomially? Linear improvement? O(n^2) to O(n)? Or if you want to be less mathematically precise: enormous improvement? Using exponential in this way in any context is a faux pas, because it's highly ambiguous, and requires context for clarification. But in this situation the context clearly resolved to the mathematically accurate definition, except it was used in the other way.
- globular-toast 1y agoRuntimes dropped precipitously.
- ndriscoll 1y agoQuadratically doesn't have the same punch because it is actually exponentially less than exponentially. So doing it for extra punch (as opposed to not knowing the correct word) in a technical context would just be lying. It'd be like a paper saying they had a result with p less than one in a trillion for "extra punch" when they actually had p=0.1.
- IshKebab 1y agoYou should if you expect your readers to be normal humans who understand obvious context, and not pedantic HN readers who understand obvious context but delight in nit-picking it anyway.
- Dylan16807 1y agoYou can, but it's not should.
- morepedantic 1y ago>pedantic Who the fuck do you think is the intended audience for an article about an algorithm in `git bundle create`? I spent approximately two minutes of my life trying to figure out where the O(n^2) algorithm was being invoked in such a way that it influenced an exponential. Exponential was bolded in the same sentence as a big-O. 50/50 troll/author oversight.
- saagarjha 1y agoMaybe not 'morepedantic
- globular-toast 1y agoAh yes because "normal humans" know what O(n^2) means but damnit they are going to use exponential wrong.
- tomjakubowski 1y agoI'm a normal human and I know what O(n^2) means. There are dozens of us.
- sneak 1y ago“Words mean things.” If you can’t agree with this, then you shouldn’t be speaking or writing, IMO. Those who argue that words that mean different things are actually equivalent have no business dealing with language.
- morepedantic 1y agoI understood every word, phrase, and sentence you wrote. But I did not understand your point. Still, I got the meaning of your words, so presumably you're satisfied.
- hskalin 1y agoI find the whole article rather poorly written. Most likely using an LLM.
- morepedantic 1y agoEspecially when the colloquial meaning derives from the mathematical meaning.
- MyFedora 1y agoWe simplify the big O notation in computer science. This is standard practice.
- rovr138 1y agoJust drop the constants, it doesn't matter /s Production systems running and melting here...
- deleted 1y ago[deleted]
- morepedantic 1y ago>Ultimately, we traced the issue to a 15-year-old Git function with O(N²) complexity and fixed it with an algorithmic change, reducing backup times exponentially. No, not in the exact same sentence as a big-O. That's either author error, or an intentional troll. Either way it's egg on their faces.
- deleted 1y ago[deleted]
- marcellus23 1y agoMeaningless and non-constructive pedantry.
- chrisweekly 1y agoI'm not the OP you're responding to, but to be fair, in a sentence about big-O perf characteristics, which includes the word "algorithms", using "exponentially" in a colloquial non-technical sense is an absolutely terrible word choice.
- linguistbreaker 1y agoExponentially bad word choice even... since we're using that word however we want now? I don't think this is meaningless or non-constructive pedantry - we're a technical community and those are technical words.
- deleted 1y ago[deleted]
- msgodel 1y agoI disagree. Misuse of the word "exponential" is a major pet peeve of mine. It's a particular case of the much more common "use mathematically precise phrasing to sound careful/precise" that you often find in less than honest writing. Here they are actually using it to refer to growth functions (which is rare for this error) and being honest (which is also rare IMO) but it's still wrong. They should have written about quadratic or quadratic vs linear. Regardless sloppy language leads to sloppy thought.
- keybored 1y agoSloppy writing is up orders of magnitude lately.
- 0cf8612b2e1e 1y agoIt will decimate readership.
- csnweb 1y agoIf you replace an n^2 algorithm with a log(n) lookup you get an exponential speed up. Although a hashmap lookup is usually O(1), which is even faster.
- ryao 1y agoThat is not true unless n^C / e^n = log(n) where C is some constant, which it is not. The difference between log(n) and some polynomial is logarithmic, not exponential.
- csnweb 1y agoBut if you happen to have n=2^c, then an algorithm with logarithmic complexity only needs c time. Thats why this is usually referred to as exponential speedup in complexity theory, just like from O(2^n) to O(n). More concretely if the first algorithm needs 1024 seconds, the second one will need only 10 seconds in both cases, so I think it makes sense.
- ryao 1y agoN is a variable in what I posted, not a constant.
- wasabi991011 1y agoIt depends if you consider "speedup" to mean dividing the runtime or applying a function to the runtime. I.e. you are saying and f(n) speedup means T(n)/f(n), but others would say it means f(T(n)) or some variation of that.
- morepedantic 1y agoThe man, or llm, used the mathematically imprecise definition of exponential in a sentence with a big-O notation. I don't think he's going to be writing entire arguments formally.
- ndriscoll 1y agoThey're still using the map in a loop, so it'd be nlogn for a tree-based map or n for a hash map.
- sn9 1y agoThe algorithm complexity went down in the function they patched (6x improvement in their benchmark), but in the context of how they benefited with how they were using the algorithm the impact was much larger (improved to taking 1% of the time), which is plausibly exponential (and figuring out the actual complexity is neither relevant nor an economic use of time).
- ndriscoll 1y ago> figuring out the actual complexity is neither relevant nor an economic use of time The fix was replacing a nested loop with a map. Figuring out that this goes from O(n^2) to O(n) (modulo details like bucket count) is immediate if you know what the words mean and understand enough to identify the problem and make the fix in the first place.
- sn9 1y agoYes that's the algorithmic complexity of the function they patched.
- wasabi991011 1y agoI interpreted that as n->log(n) since log and exp are inverses. Also because I've often heard tha the quantum Fourier transform is an exponential speedup over the discrete Fourier transform, and there the scaling goes n^2->nlogn.
- morepedantic 1y agoI was also looking for the exponential algorithm.
- abhashanand1501 1y agoIn fact O(n^2) is exponentially more than O(log n).