I started reading the Competitive Programmers Handbook, and on page 20 the author writes about varying algorithmic complexity classes. When covering √, he writes:
O(√) A square root algorithm is slower than O(log) but faster than O().
A special property of square roots is that √ = /√, so the square root √ lies, in some sense, in the middle of the input.
I'm not entirely sure what he means by the middle of the input; is he just saying that √ is just somewhere between within the range [1, ]? If that's the case, log satisfies the same property, and I don't see why it's notable to bring up.
log = O(√) and √ = O(), so it is clear that O(√) lies between these two other well-defined classes, but I wonder if anyone has insight as to what the "middle of the input" is supposed to mean in this context.
"The middle of the input" here means a geometric middle, i.e. when 1 and are the first and third term in a geometric sequence, then √ is the second ("middle") one.
An example is where you divide an input array with elements into √ buckets. By consequence of this "special" property of the square root, these buckets will each have approximately √ elements. See for example jump search. The choice of √ is a kind of optimum here: if you would divide the array into fewer buckets, you'd have more elements per bucket, and so more work to do. If you would divide the array into more buckets, you have more buckets to process, again increasing the work to do. So here you get a feel of this "middle".