The distance between the n-dimensional points (0,0,...,0) and (1,1,...,1) is sqrt(n). So if you move sqrt(n) units along that diagonal, you move 1 unit along the dimension that matters. Or if you move 1 unit along the diagonal, you move 1/sqrt(n) units along that dimension. 1/sqrt(n) efficiency.
If you instead move 1 unit in a random direction then sometimes you’ll move more than that and sometimes you’ll move less, but I figured that was unimportant enough on net to leave it O(1/sqrt(n)).
The distance between the n-dimensional points (0,0,...,0) and (1,1,...,1) is sqrt(n). So if you move sqrt(n) units along that diagonal, you move 1 unit along the dimension that matters. Or if you move 1 unit along the diagonal, you move 1/sqrt(n) units along that dimension. 1/sqrt(n) efficiency.
If you instead move 1 unit in a random direction then sometimes you’ll move more than that and sometimes you’ll move less, but I figured that was unimportant enough on net to leave it O(1/sqrt(n)).