Notable examples of the square root idea in complexity analysis
There are $O(m^{3/2})$ triangles in any $m$-edge graph and that they can be found in $O(m^{3/2})$ time. There are many ways of doing this but I think one of the earliest is Itai and Rodeh (STOC 1977) who provide an algorithm that goes through a sequence of linear-time iterations, each of which removes a spanning forest from the graph. In the early iterations when the remaining forest has at least $n-k$ components, the algorithm removes at least $k$ edges per step, and in the late iterations when it has at most $n-k$ components, the maximum degree is $k$ and shrinks by at least one in each step. So the total number of iterations is at most $m/k+k$ and choosing the right tradeoff gives the overall bound of $O(\sqrt m)$ on iterations and $O(m^{3/2})$ on time.