No it doesn't, it just improves the constant factor by a lot. Unless you are thinking of block sparse attention, which can chance complexity (assuming you scale sparsity with size) but decreases quality.