あるデータ処理アルゴリズムについて、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)である。
アとイのみが正しいそうですが、その理由が分かりません。どなたか教えて下さいませんか。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2020/10/17 23:45

https://oshiete.goo.ne.jp/qa/11946684.html
とはなにがちがう?

この回答へのお礼

仰る通りです。大変失礼致しました。ご指摘感謝申し上げます。

お礼日時：2020/10/18 09:09