算法复杂度表达式O(n) ∈ O(ƒ)是否正确？

这个表达式仅当f(n)是n的渐近上界时成立，也就是在特定条件下是正确的。

大O符号的本质是描述函数的渐近上界，它代表的是一组函数的集合：

• O(n)是所有增长速度不超过线性函数的函数构成的集合
• 当f(n)的增长速度不慢于n时（比如典型例子f(n) = n log n），O(n)中的每一个函数都满足O(f)的定义，因此O(n)这个集合是O(f)集合的子集，此时O(n) ∈ O(f)的关系成立。

反过来，如果f(n)的增长速度比n慢（比如f(n) = 1），那么O(n)中的函数并不都属于O(f)，这个表达式就不成立。

内容的提问来源于stack exchange，提问作者Daniel Bustamante