I'm not entirely convinced that the Newton solution is really all that much better than the binary search log(n) solution.

Obviously, it takes more than one pass for the Newton solution to achieve the correct result. In fact, it takes *many* passes to reduce the initial "guess" to the square root of n. If you try it with the max integer size, 2147483647, Newton's iteration takes 20 cycles to even get to the correct integer value (and then has to continue cycling through ever-decreasing decimals). A log(n) binary search, on the other hand, takes 31 iterations, max.

Knowing that, it seems a little disingenuous to call Newton's iteration solution a constant-time solution when it's arguably not really any better than a log(n) search. If you were asked this question in an interview, I feel that the binary search method would be the best way to handle this problem, especially since Newton's iteration is something you either know or you don't - you aren't expected to derive it yourself in a 30 minute interview.

Is there anyone who knows the true Big O of Newton's iteration solution?