241–250 of 273 posts
Earlier quoted context omitted.
Skiena has a great table in his algorithms book mapping time complexity to hypothetical times for different input sizes. For n of 10^9, where lg n takes 0.03 us and n takes 1 s, n lg n takes 29.9 s and n ^2 takes 31.7 years .
more from table please?
Earlier quoted context omitted.
They’re too ridiculous… unless a more optimal solution does not exist
Absolutely not. If the cost of doing something goes above quadratic, you shouldn't do it at all. Because essentially every customer interaction costs you more than the one before. You will never be able to come up with ways to cover that cost faster than it ramps. You are digging a hole, filling it with cash and lighting it on fire. If you can't do something well you should consider not doing it at all. If you can on…
Earlier quoted context omitted.
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.
Earlier quoted context omitted.
To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
Fair, but `n log n` definitely is the historical "good enough to actually sleep at night" in my head, every time I see it I think of the prof who taught my first CSC course and our data structures course due to how often it came up. Also, the wise statement that 'memory is fairly cheap compared to CPU for scaling'. It's insane to see how often folks would rather manually open and scan a 'static-on-deploy' 20-100MB Js…
Earlier quoted context omitted.
Not often but occasionally I will chose the nlogn algorithm which obviously has no bugs over the O(n) algorithm with no obvious bugs. Less brittleness is worth paying a few percent. Especially if it unmuddies the waters enough for someone to spot other accidental (time) complexity.
Considerably more than a few percent, IMHO. :) But I also don't dabble in this area nearly enough to know whether there's years of tears and toil finding out repeatedly that O(n) is ~impossible to implement and verify :) | n | n log n | | 5 | 8.0472 | | 10 | 23.0259 | | 25 | 80.4719 | | 50 | 195.6012 | | 100 | 460.5170 |
If you expect that n will always hold, it may be better to implement the O(n) algorithm and add a logging warning if n > 250 or so (and, maybe, a fatal error if n > 1000 or so), instead of spending time to write both versions of the algorithm and spend time finding the cut off value for choosing between the two.
Earlier quoted context omitted.
They weren't, if you look at the fix [1] the dedupe loop was run in all cases, not just those with known dupes, so the performance hit was any bundle with lots of refs. 1. https://github.com/git/git/commit/bb74c0abbc31da35be52999569...
But why couldn't they just dedupe the refs from the command line before starting the actual bundling - surely there are never more than a couple of hundred of those (one per branch)?
"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.
Earlier quoted context omitted.
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.
Ah yes because "normal humans" know what O(n^2) means but damnit they are going to use exponential wrong.