lkozma
Joined 19 years ago
Karma
3,580
Submissions
780
Member since
Mar 27
Recent submissions
Comment · 3 years ago
My favorite artistic illustration is probably Jorge Stolfi's drawing inspired by the self-adjusting splay tree data structure of Sleator and Tarjan:
https://www.link.cs.cmu.edu/splay/tree5.jpg
Comment · 3 years ago
Yes, this efficiency-aspect is not captured in the illustration -- while splitting perfectly _by index_ comes for free, splitting perfectly _by value_ needs nontrivial work (median-finding).
Comment · 3 years ago
May I add one that I made?
Illustration of QuickSort and MergeSort as two sides of the same coin: http://lkozma.net/images/sort/duality.pdf
I find this somehow both obvious and counter-intuitive, and usually the two algorithms are not presented in this way, as duals of each other.
I wrote up this view in more detail, but the figure above should be self-explanatory: http://lkozma.net/blog/a-dual-view-of-sorting-algorithms/
Comment · 4 years ago
Socrates supposedly loved going to the market. When his students asked him about this, Socrates replied, "I love to go and see all the things I am happy without." :)
Comment · 4 years ago
This is a very nice and deep question. Are you aware of the published research on the problem?
The growth rate is indeed around 4 and now known to be strictly above 4: https://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf
If I remember correctly, there was a non-rigorous argument for a concrete conjectured value not far above 4.
Comment · 4 years ago
"Seeing an astronomer using a telescope to observe a galaxy, no-one will confuse the telescope with the galaxy. Mathematics differs from science in that there is no clear distinction between the tools and the objects of study." -- D.Aldous
Comment · 4 years ago
You are right in general, but when the quote is from someone on whose research the result builds in an important way (as it is the case here), I would say it is fair.
Comment · 4 years ago
Your first point is correct, but just to clarify your second point, these two definitions are not quite equivalent, as there is a world of functions growing more quickly than log^k(n) no matter how large constant k, but still within n^o(1).
For an example, consider 2^sqrt(log(n)).
This is a bit similar to something being faster than polynomial, but slower than exponential.
[email protected]