I have just learnt Big-Oh notation and saw the below problem:

(1) Is T(n) = 10n^4   850n = O(n^3) ??
(2) Is T(n) = 10n^4   850n = O(n^4) ??
(3) Is T(n) = 10n^4   850n = O(n^30) ??

I have understood (1) that Big-Oh represents the upper bound and hence it cannot be O(n^3) and hence (1) is false. Similarly, (2) is true.

With regard to (3). Should it be true? If T(n) for an algorithm is say linear, can we also represent it in O(n^2) etc as Big Oh depicts the upper bound ?

CodePudding user response：

Formally it is true, yes. To represent precise ("tight") bounds, the big Theta (Θ) notion is used instead, whereas big Oh allows the complexity to be lower that stated. (If the question requires you to give a single answer, they probably meant the second, though.)