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/

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.

For an example, consider 2^sqrt(log(n)).

This is a bit similar to something being faster than polynomial, but slower than exponential.

frequentist :: Bayesian ~ worst-case analysis :: average-case analysis

There are a good reasons why we don't usually do average-case analysis of algorithms, chief among them that we have no idea how inputs are distributed (another reason is computational difficulty). Worst-case bounds are pessimistic, but they hold.

Comments URL: https://news.ycombinator.com/item?id=29628769

Points: 10

# Comments: 0

The door refused to open. It said, "Five cents, please." He searched his pockets. No more coins; nothing. "I'll pay you tomorrow," he told the door. Again he tried the knob. Again it remained locked tight. "What I pay you," he informed it, "is in the nature of a gratuity; I don't have to pay you." "I think otherwise," the door said. "Look in the purchase contract you signed when you bought this conapt." In his desk drawer he found the contract; since signing it he had found it necessary to refer to the document many times. Sure enough; payment to his door for opening and shutting constituted a mandatory fee. Not a tip. "You discover I'm right," the door said. It sounded smug. From the drawer beside the sink Joe Chip got a stainless steel knife; with it he began systematically to unscrew the bolt assembly of his apt's money-gulping door. "I'll sue you," the door said as the first screw fell out. Joe Chip said, "I've never been sued by a door. But I guess I can live through it."

(Philip K. Dick: Ubik)

To add more nuance, there is an essay [1] telling the history of early maximum flow algorithms and includes this small anecdote:

[An] American asked: ".. how were you able to perform such an enormous amount of computing with your weak computers" to which the Russian responded: "we used better algorithms".

There is some truth to that, besides maximum flow, similar stories can be told about linear programming, data structures (e.g. AVL-trees), numerical computing, etc. The hardware may have been sloppy, but the algorithms-research was top notch.

[1] http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf

To improve this situation you can use an additional trick: keep track of the sequence of thrown-away pairs, and look at them again in consecutive pairs, and generate some more random bits:

* 00 00 -- throw away

* 11 11 -- throw away

* 00 11 -- output 1

* 11 00 -- output 0

and so on..

see the paper "Iterating Von Neumann's Procedure for Extracting Random Bits" for details.

Comments URL: https://news.ycombinator.com/item?id=28326145

Points: 3

# Comments: 0

After misclicking hundreds of times, I still couldn't train myself to go against my perception and follow the designer's "bold vision", using it feels like writing with my left hand or steering a bicycle with a crooked wheel.