It's an open ended optimization problem. You can get bad results very quickly but on high quality settings it can take minutes or hours to compress large textures.

And the newer compression formats have larger block sizes from 8x8 to even 12x12 pixels. ASTC and BC7 are a different beast to the early texture compression formats. You can get pretty awesome image quality at 2 bits per pixel (and slightly less awesome at less than a bit per pixel).