algorithm - big O in algorithm

Question

I have read the definition of big O in the introduction to algorithm which book doesn't talk about my confusion.

According to its definition, everybody knows the function T(n) = 3n belongs to O(n),my confusion is whether all functions what belongs to O(n) belongs to O(n^2) and O(n^3) and O(n^4) and O(n^k) k>1, because the big O describes the upper limit,and I aways can find the positive integer constant c and positive integer constant n0 to meet 0<=3n<=cn^2 when n>=n0, if the answer is YES, why do people prefer th use O(n) to describe T(n) = 3n if its definition is serious?

More, where are these notations(big O, big theta, big omega) been used in other math field?

Please post the necessary references or any other books which talk about this

Answer 1

部分答案：您的理解是正确的，对于 k > 1，O(n) 是 O(n^k) 的严格子集。

为什么我们更喜欢 O(n)：如果您询问某种产品的价格（实际上是 25），您更喜欢哪个答案：a）最多 100 或 b）最多 30。说 f(n) 在O(n) 提供了更多关于 f(n) 的信息，而不是说它在 O(n^2) 中。

它还用在什么地方？例如描述一个近似值的误差项。

Answer 2

f(n)=O(g(n))确实表示g(n)是f(n)渐近意义上的上界，并且任何函数h(n)≥g(n)也是上界，f(n)=O(h(n)).

例如f(n)=O(n) => f(n)=O(n²).

但显然，一个更接近于目标函数建模的上界更有趣，并且被称为是紧的。因此，在可能的上限中，当已知时，选择最紧密的界限。

对于某些函数，可能会出现相同g(n)的下界（具有不同的渐近常数），我们将其表示为f(n)=Ω(g(n))。在这种情况下，两种方式的界限都很紧，一个人写f(n)=Θ(g(n)).

当然，3n=Θ(n)，但是3n<>Θ(n²)。