You're using half as much memory for something that is vaguely O(n^2), so there's your roughly 4x factor speedup. But since things aren't perfect, it ends up be

You're using half as much memory for something that is vaguely O(n^2), so there's your roughly 4x factor speedup. But since things aren't perfect, it ends up being a bit lower.