[解決済み] 再帰性 T(n) = T(n^(1/2)) + 1

質問

この再発見を見て、自分のアプローチが正しいかどうか確認したいのですが。

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

ということで、答えはn^(1/2)のシータ境界となる。

どのように解決するのですか？

のヒントがあります。 n = 2とする ^{2 m} または m = log <サブ 2 ログ <サブ 2 nとなり、2がわかると ^{2 m-1} * 2 ^{2 m-1} = 2 ^{2 m} ということで、S(m)=T(n)と定義すると、Sは次のようになります。

S(m) = S(m-1)+1 → S(m) = Θ(m) → S(m) = T(n) = Θ(log) <サブ 2 ログ <サブ 2 n)

を拡張し、一般的なケースに対応させる。

T(n) = T(n/2) + 1のような再帰では、各反復で、木の高さを半分にする。これは、Θ(logn)につながる。しかし、この場合、入力数を（2ではなく）2の累乗で割っているので、Θ(log log n ) となる。