Yes, it offends my aesthetic sense when the asymptotically fastest algorithms for simple problems are complex monsters. It didn't used to be like that: early fast algorithms (like heapsort and FFT) are only very slightly more complex than the naive ones.

Computer science was a new branch of mathematics 100 years ago. Folks discovered the easy, low-lying algorithms. I don't know about you, but I've rediscovered quite old results that are named so-and-so's algorithm or what's-their-face's theorem; because they were the obviously efficient ways of solving those problems.

Supposing P=NP, one would expect the polytime algorithm to be brain-meltingly complex. Same goes for, say, a n^2log(n) matrix multiplication algorithm.

Simplification is a really good strategy for optimizing algorithms. But sometimes, doing less work requires doing a bit of thinking upfront, or carefully cleaning up behind yourself (but not cleaning too eagerly).

I really don’t understand why this is being downvoted. Beyond trivial algorithms, as mentioned in the parent, fast algorithms come from deep knowledge of the problem, leading to highly tailored data structures, and thus very complicated algorithms. I’m not sure why this is controversial? Also citing aesthetic sensibility is fine, but it’s also fine to update or recalibrate one’s aesthetic intuition.

lol cooley-tukey FFT is anything but simple when you actually have to implement it.

Cooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago:

    def fft(x):
        N = len(x)
        if N == 1:
            return x
        assert N % 2 == 0
        E = fft(x[::2])
        O = fft(x[1::2])
        X = [None] * N
        for k in range(N // 2):
            tf = np.exp(-2j * np.pi * k / N)
            X[k] = E[k] + tf * O[k]
            X[k + N//2] = E[k] - tf * O[k]
        return X

The Wikipedia article describing it is surprisingly decent: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...

I remember showing a coworker a complexity analysis I did, where I'd written "0.002 n lg n + 3n". I was surprised when they asked "why did you put the insignificant one first?" but then realized... that's exactly right! Even for universe sized problems, 3n is more than 0.002 n lg n.

Basically, as soon as you care enough about constant factors to actually compute them, some of your habits from doing asymptotic analysis can be actively harmful.

FTA:

> This work could be viewed as another O() warning showing how important factors and even subdominant additive terms are.