Not Always Root N

$S = n/\log m$, giving $O(n \log m)$. Only when $m = \Theta(n)$ does that collapse to the $\log n$ block and the $O(n \log n)$ everyone quotes.

$S = n/\sqrt{m}$, giving $O(n\sqrt{m})$. Only when $m = \Theta(n)$ does that collapse to the $\sqrt{n}$ block and the $O(n\sqrt{n})$ everyone quotes.

$S = \sqrt{n}$, giving $O(n\sqrt{n})$ for every $m$. The block never depends on the query count, since only the right pointer's $O(n^2/S)$ term matters.

$S = \sqrt{m}$, giving $O(m\sqrt{n})$. Only when $m = \Theta(n)$ does that collapse to the $\sqrt{n}$ block and the $O(n\sqrt{n})$ everyone quotes.