News for hackers. Stuff that matters.
Re:New Book-Sorting Algorithm Almost Reaches Perfection by thaumasiotes on Friday January 24, 2025 @03:11PM (#42816502)
> lowering the upper bound to (log n) times (log log n)^3 — equivalent to (log n)^(1.000...1)

This is true! One of the things I find cool about big-O complexity using polynomial reference classes is that logarithms give you an infinitesimal value. Take that, "infinitesimals don't really exist" people!

Re:New Book-Sorting Algorithm Almost Reaches Perfection by sfelicio on Friday January 24, 2025 @05:45PM (#42817659)
Wait. What? Do you have a reference where I can learn about this?
Re:New Book-Sorting Algorithm Almost Reaches Perfection by thaumasiotes on Saturday January 25, 2025 @12:48AM (#42819790)
I don't really understand what you're asking for. You can easily just verify the claim for yourself.

The limit as x goes to infinity of (ln x) / (x^k) is zero for all positive k. So if you want to approximate the behavior of a logarithm with a function of the form f(x) = x^k, k must be greater than 0 [because x^0 = o(ln x)], but less than every positive real number. This is the definition of an infinitesimal.

That's why it makes sense to say that x (log x)^3 is equivalent to x^{1.000000...[infinite 0s]...1}. Though in this analogy, it's more like x^{1.000000...3}.

Re:New Book-Sorting Algorithm Almost Reaches Perfection by da39a3ee on Saturday January 25, 2025 @08:14AM (#42821456)
[delayed]
Re:New Book-Sorting Algorithm Almost Reaches Perfection by User23 on Saturday January 25, 2025 @09:28AM (#42821841)
Only believing things that you can easily reason through if you are presented with some external authority really is a cognitive antipattern though.

I’d say that prologue was more medicinal than condescending. It’s good to remind people in the age of LLMs and ubiquitous search that “you can just think things.”

Re:New Book-Sorting Algorithm Almost Reaches Perfection by thaumasiotes on Saturday January 25, 2025 @03:54PM (#42824776)
OK. What reference would you point them to? What makes you think it's what they want?