オーダー評価について

Question

2n+5=O(n)が成り立つことを証明せよ。

解答
2n+5≤2n+5n=7nがn≥1で成り立つから，n0=1およびC=7とすれば，n≥n0=1を満たす全ての自然数nに対して，2n+5≤Cn＝7nが成り立つ。ゆえに，2n+5=O(n)である。

とあるのですが授業を聞いていても本当によくわかりませんでした。
最初の「2n+5≤2n+5n=7nがn≥1で成り立つ」から理解していないです。
なぜ「2n+5」の5に「n」がつくのですか？そのレベルで理解できていないです。
頭が悪い僕でもわかりやすく教えてほしいです。よろしくお願いします。

Comments

[Zuishin]

2×n+5 と (2×n)+(5×n) の大小を比べてみましょう。
n は自然数なので、n が 1 の時、2 の時、3 の時と順番に計算していけばわかります。

例えば n が 0 の時、5 は 5n より大きくなりますが、1 の時、5 と 5n は同じです。2 の時には 5n の方が大きくなります。3、4 と数が増えるに従って差は広がるばかりで、5n は 5 より小さくなることはありません。n は 1 以上という条件がついているので、5n は必ず 5 以上になります。

Answer 1

「なぜ付くか」というのはあまり問題ではありません。最終的に
2n+5≤(正の定数)×n
が1以上の整数nに対して成り立つ、という「事実」を示せれば証明ができます。

今、1≤nの時、両辺に5を掛けることにより
5≤5n が言え、さらに両辺に2nを加えて
2n+5≤2n+5n が言えます。

Comments

[rarirureroo]

ありがとうございます！助かりました！

Answer 2

まずランダウの記号 O(・) の定義を確認し、「2n+5=O(n)が成り立つことを証明」するには具体的になにを示せばいいのかを確認しましょう。

ランダウの記号 - Wikipedia

---