3 ms·

I always have trouble thinking of computation in terms of “bits erased”. How many bits are erased when I sort an array? Or invert a matrix? Or compute a functio

I always have trouble thinking of computation in terms of “bits erased”. How many bits are erased when I sort an array? Or invert a matrix? Or compute a function like f(x)=1, which seems to maximally erase information, but doesn’t intuitively seem like it should cost a lot of energy.

aifer4 3y ago
To answer your question about sorting an array: For an array of length n, where each element takes one of m possible values, there are n^m possible arrays. But there are only O(n^m/n!) possible sorted arrays, which could be crudely approximated as O(n^(m-n)). The decrease in information is proportional to the log of the ratio of the number of possible states before and after the computation, which is in this case log(n^n) = n log n. See another explanation here https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall07/Lectures/sortLB.pdf https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall07/...