用大哦证明小哦

Question

如果我已经知道 f(n) 是 O(g(n))。从little-oh的定义，如何证明f(n)是o(n * g(n))？

Answer 1

鉴于：f(n) is in O(g(n))。

使用 big-O 符号的定义，我们可以将其写为：

f(n) is in O(g(n))

=> |f(n)| ≤ k*|g(n)|, for some constant k>0                 (+)
                      for n sufficiently large (say, n>N)

如上使用的big-O的定义，参见例如

https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation

证明：给定(+)，然后f(n) is in o(n*g(n))。

让我们首先说明 little-o 符号的含义：

Formally, f(n) = o(g(n)) (or f(n) ∈ o(g(n))) as n → ∞ means that for every positive constant ε there exists a constant N such that
|f(n)| ≤ ε*|g(n)|, for all n > N                          (++)

来自 https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation.

现在，使用(+)，我们可以写

|f(n)| ≤ k*|g(n)|, som k>0, n sufficiently large 

    <=> { n > 0 } <=> n*|f(n)| ≤ k*n*|g(n)|
                  <=> n*|f(n)| ≤ k*|n*g(n)|
                  <=>   |f(n)| ≤ (k/n)*|n*g(n)|            (+++)

Return 到 little-o 的定义，特别是 (++)，并且在不失一般性的情况下，固定 k。现在，每个正常数 ε 都可以描述为

ε = k/C, for some constant C>0 (with k fixed, k>0)         (*)

现在，在不失一般性的情况下，假设 n 大于此 C，即 n>C。然后，(*) 和 (+++) 产生

|f(n)| ≤ (k/n)*|n*g(n)| < (k/C)*|n*g(n)| = ε*|n*g(n)|      (**)
                        ^                ^
                        |                |
                    since `n>C`         (*)

由于我们正在研究渐近行为，我们可以选择将 n 的下限分配给任何大于 C 的值（事实上，这在 big-O 和 little-o, "n sufficiently large"), 因此---根据上面 little-oh 的定义---, 我们有：

- As shown above, (+) implies (**) 
- By the definition of little-o, (**) shows that f(n) is in o(n*g(n))
- Subsequently, we've shown that, given (+), then: f(n) is in o(n*g(n))

Result：如果f(n) is in O(g(n))，则f(n) is in o(n*g(n))，这两个关系指的是big-O和litte-O渐近界，分别

评论：结果其实很微不足道。 big-O 和 little-o 符号仅在用于证明上限的两个常量之一不同，即，我们可以将 big-O 和 little-O 的定义写为：

f(n) 如果我们能找到一组正常数 (k, N)，则称 f(n) 在 O(g(n)) 中，这样 f(n) < k*g(n) 对所有n>N.
f(n) 如果我们能找到一个正常数 N，那么 f(n) < ε*g(n) 对所有 n>N，和 对于每个正常数 ε。

后者显然是一个更严格的约束，但是如果我们可以在 f(n) < ε*g(n) 的 left-hand-side 中使用 n 的一个额外幂（即 f(n) < ε*n*g(n) ), 那么即使 ε 的无穷小值, 我们也总是可以自由选择另一个常数 N 足够大 ε*n 来为我们提供任何常数 k 可以是用于显示 f(n) 在 O(g(n)) 中（回想一下，n>N）。

用大哦证明小哦

Prove small-oh with big-oh

algorithm

big-o