Randomized algorithms are so damn cool. They really feel like cheating your way out of NP problems. I highly recommend that anyone interested in algorithms studies them.

▲

gnull 6 hours ago | parent | next [-]

https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf

Then you reach derandomization and it hits you once again, it shows you that maybe you can "cheat" in the same way without randomness. Not for free, you usually trade randomness for a bit more running time, but your algorithms stay deterministic. Some believe all probabilistic algorithms can be derandomized (BPP = P), which would be a huge miracle if true.

▲

another_twist 9 hours ago | parent | prev [-]

+1. My favourite bit is when pivots are chosen randomly in quicksort, we get linearithmic expected complexity. The CLRS proof using indicator random vars was a oh-shit moment.

	▲	tmoertel 3 minutes ago \| parent \| next [-]
		Similarly, quickselect with random pivots runs in expected linear time. For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycoding...
	▲	11 minutes ago \| parent \| prev \| next [-]
		[deleted]
	▲	gnull 6 hours ago \| parent \| prev [-]
		Btw, you can make quicksort deterministically O(n log n) if you pick the pivot point with linear median search algorithm. It's impressive how randomness lets you pick a balanced pivot, but even more impressive that you could do the same without randomness.