渐近分析“o”到“O”的转换
我对“O”和“O”符号的理解是前者是上限，后者是严格的限制。 我的问题是，如果一个函数f（n）被一些随机函数严格约束，比如说o（g（n））。 通过乘以某个常数“c”，即使当n>无穷大时，它也是一个上界，可以将这个界限作为一个上界，即（O（g（n））。
本质上，f∈O（g）表示
对于常数k> 0的至少一个选择，可以找到一个常数a，使得对于所有x> a，不等式0 <= f（x）<= kg（x）。
请注意，O（g）是此条件成立的所有函数的集合。
基本上，f∈o（g）表示
对于常数k> 0的每一个选择，你可以找到一个常数a，使得对于所有x> a，不等式0 <= f（x）<kg（x）。
再次注意，o（g）是一个集合。
维基百科：
注意大O符号的早期形式定义与小O的当前定义之间的区别：前者对于至少一个常数M必须是正确的，后者必须对每个正常数ε保持不变，但是很小。 这样，小O符号比相应的大O符号有更强的说法： 每个g的小函数也是g的大-O，但并不是每个函数都是大-O的g也是g的小数 （例如g本身不是，除非它在∞附近相同为零）。
这个链接包含很好的解释：
http://www.stat.cmu.edu/~cshalizi/uADA/13/lectures/app-b.pdf