The bzip2 algorithm is, as I recall, quadratic in block size. But that's because of the implementation, ways to do the BWT transform in linear time has been fou

The bzip2 algorithm is, as I recall, quadratic in block size. But that's because of the implementation, ways to do the BWT transform in linear time has been found since. And also, bzip2 doesn't let you choose very big block sizes anyway, it could have supported far larger ones with the memory modern computers have (as opposed to when it was first implemented)