あるデータ処理アルゴリズムについて、n個のデータを処理する際の計算量T(n)に対して、次の式が成立す

あるデータ処理アルゴリズムについて、n個のデータを処理する際の計算量T(n)に対して、次の式が成立する。
T(1)=0
T(n)=T(n/2)+c (nが偶数のとき)
T(n)=T(n-1)+c (nが3以上の奇数のとき)
ただし 、cは正の定数とする。
このとき、次の記述ア、イ、ウについて、
ア：全ての正整数nに対してc•log_[2]n≦T(n)である。
イ：全ての正整数nに対してT(n)≦2c•log_[2]nである。
ウ：全ての正整数m、nに対してm<nならばT(m)≦T(n)である。
アとイのみが正しいそうですが、その理由が分かりません。どなたか教えて下さいませんか。

質問者からの補足コメント

• 具体的にどうやって帰納法で確かめれば良いかを教えて下さいませんか。

    補足日時：2020/10/14 07:28

No.1 回答者： Tacosan 回答日時： 2020/10/10 23:21

帰納法でがんばる.

No.2 回答者： Tacosan 回答日時： 2020/10/14 18:11

・n=1 で成り立つことを示す.

・n < k で成り立つと仮定して, n=k でも成り立つことを示す.

もちろん「成り立たない」ものは帰納法では証明できないのでそこは注意してほしい.

この回答へのお礼

簡潔で分かりやすい解説に感謝します。

お礼日時：2020/10/15 08:14