¡Buenas!

En este caso si que infuye una cuenta mas que una menos. Una algoritmo es de orden O(n) y el otro de orden O(n^1/2. Si tienes que s(n/k) = n/(kn^1/2) y haces limite de s(n) en +infinito, te dara +infinito. Esto quiere decir que n crece mucho mas que n^1/2, para numeros grandes, lo que significa que hacer comparaciones hasta la raiz cuadrada es mas eficiente que hacerlo hasta el mismo numero o hasta su mitad.

¡Saludos¡