大O符號證明

Question

我試圖證明這個公式（N +1）/（N + 1）是O（n）的

如你所知，我們需要拿出n0和C。

所以我對如何選擇合適的C感到困惑，因爲這裏的公式是除法。

因此，與C = 1，（N 1）/（N + 1）/ n的

（N + N）/（N + N）/ ñ> = （N 1）/（N + 1）

但我在如何這裏簡化除法此處卡住。

Answer 1

當n趨向無窮大原來的方程爲n^2/N這相當於爲O（n）

Answer 2

選擇c = 1：

(n^2 + 1)/(n + 1) <= 1*n  definition of Big-Oh with c = 1 
n^2 + 1 <= n^2 + n    multiplying both sides by n + 1 
1 <= n       subtracting n^2 from both sides 
n >= 1       rearranging 

因此，選擇n0 = 1作品c = 1。