Hacker News Reader

Comment by hiddew | Hacker News Reader

"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.

This is not the precise mathematical definition of exponential, but rather the colloquial one, where it just means "a lot".

You 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.

I somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch

“Dramatically” ?

"a lot"

"by a factor of `n`" also sounds impressive.

If you just mean "a lot" in a non-technical sense, there are plenty of words available. enormously. immensely. tremendously. remarkably. incredibly. vastly.

“From quadratic to linear” seems fine.

“From quadratic to linear” or “... to constant” seems fine.

Algorithmic? 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.

Runtimes dropped precipitously.

Quadratically 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.

You 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.

You can, but it's not should.

>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.

Maybe not 'morepedantic

Ah yes because "normal humans" know what O(n^2) means but damnit they are going to use exponential wrong.

I'm a normal human and I know what O(n^2) means. There are dozens of us.

“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.

I 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.

I find the whole article rather poorly written. Most likely using an LLM.

Especially when the colloquial meaning derives from the mathematical meaning.

We simplify the big O notation in computer science. This is standard practice.

Just drop the constants, it doesn't matter /s

Production systems running and melting here...

>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.

The 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).

> 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.

Yes that's the algorithmic complexity of the function they patched.

If 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.

That 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.

But 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.

N is a variable in what I posted, not a constant.

It 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.

The 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.

They're still using the map in a loop, so it'd be nlogn for a tree-based map or n for a hash map.

I 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.

Meaningless and non-constructive pedantry.

I'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.

Exponentially 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.

I 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.

Sloppy writing is up orders of magnitude lately.

It will decimate readership.

My personal pet peeve is when the term “exponentially” is used to refer to a change between precisely two data points.

It’s a very specific subset of the one you’re describing.

“Tell me you don’t know what you’re talking about without telling me you don’t know what you’re talking about.”

>My personal pet peeve

Just be glad you have only one.

>pedantry

I wasted 2 minutes of my life looking for the exponential reduction. So did many others.

Now I'm wasting more of my life shit posting about it, but at least that's a conscious choice.

No, you spent 2 minutes improving your reading comprehension.

You're insulting people on the internet AND you're wrong, which puts you one Hitler comparison away from the trifecta.

In fact O(n^2) is exponentially more than O(log n).

I was also looking for the exponential algorithm.

Reply on news.ycombinator.com