大 O 表示法中的常数 c

Question

假设 f(n) 是算法的运行时间。

根据 的函数定义O(n)，if f(n)<=c*g(n)then f(n)=O(g(n))where n0<=n。

常数c的取值范围是多少？

Answer 1

根据定义（例如此处），任何正数，只要它是常数。

例如，n^2不在中，O(n)因为没有正数c使得n^2 = cn对于所有n；该等式可以简单地求解为c = n，但根据定义n它不是一个常数。