performance - 证明时间复杂度函数的效率等级

下面是解决办法，但我有困难理解1部分的证明归纳部分为什么你只能在一边加+2，另一边加+4？
我们正在处理函数T(n) = 2n + 2
我们想找到一个c，使得对于大n
我们有T(n) <= c * f(n)和T(n) = 2n + 2，所以我们需要f(n) = n
我们求解c，得到2n + 2 <= c * n
2 + 2/n在n=0时未定义，因此我们选择2/n我们会选择t >= 1，所以t=1
归纳证明：

         T(n) <= c * f(n)
     (2n + 2) <= (4)(n)
          +2     +4              <---- Don't understand
      2n + 4  <= 4n + 4
2(n + 1) + 2  <= 4(n + 1)
     T(n + 1) <= c * f(n + 1)

结论：
2n+2∈O（n）

最佳答案

如果2n+2 <= 4n，左手边加2，右手边加4，左手边就少了，所以如果2n+2 <= 4n，定义为2n + 2 <= 4n + 4
所以，你基本上从2n+2 <= 4n（从归纳假设中你知道这是真的）跳到2n+4 <= 4n+4，因为2<4和2n+2<=4n。稍后您会发现，诱导子假说的主张对于下一行中的n+1也是正确的。

关于performance - 证明时间复杂度函数的效率等级，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25909772/