[hiddew]

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

[umanwizard]

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

[cvoss]

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.

[morepedantic]

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

[sn9]

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

[ndriscoll]

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

[csnweb]

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.

[ryao]

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.

[ndriscoll]

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.

[wasabi991011]

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.

[marcellus23]

Meaningless and non-constructive pedantry.

[chrisweekly]

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.

[msgodel]

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.

[morepedantic]

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

[abhashanand1501]

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

[morepedantic]

I was also looking for the exponential algorithm.