原です。

>近岡です。

>2進数での開平法は、2分法で平方根を求めることと同じ。
>ループの回数は求める桁数に比例しますから、
>整数iの平方根の整数部分を求める場合の
>実行時間のオーダーはO(log(i))ですね。
>
>ニュートン法で平方根を求める上記の方法では、
>    while (s < t) { s <<= 1; t >>= 1; }
>
>    do { t = s; s = (x / s + s) >> 1; } while (s < t);
>の2つのループがあります。
>実行時間のほとんどをしめると思われる2つ目のループの回数は
>求める桁数の対数にほぼ比例しますから、
>整数iの平方根の整数部分を求める場合のオーダーは、
>O(log(log(i)))ですね。(今一つ自信がありませんが)

前半と後半を合わせると

 O(log(i)) + O(log(log(i))) = O(log(i))

となるのでは。