大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。