Question & Answer: Using the definitions of O and Ohm show that 6n^2 + 20 n elementof (n^3) but 6n^2 + 20 NotElement n Ohm (n^3)…..

Definition of O and  :

• O : The function f(n) = O(g(n)) iff there exists positive constants C and n₀ such that f(n) <= C*g(n) for all n > n₀.

Here , f(n)= 6n² + 20n

6n² + 20 n <= 10* n³ n > 1

Here , g(n) = n³

C= 10, n₀ = 1, both are positive constants.

 f(n)  O(n³)

•  : A function f(n) = (g(n)) iff there exists positive constants C and n₀ such that f(n) >=C* g(n)  n>=n₀

Here f(n) = 6n² + 20n

6n² + 20n >= n³ when n > 1 && n<6. But for values of n>6, this doesn’t hold true.

Here g(n) = n³

C=1

 f(n) (n³) .

Whereas, 6n² + 20n > 6n² ,  n>1

Here g(n) = n²

C = 6 and n₀ = 1.

 f(n) (n²)

Therefore, 6n² + 20n = O(n³) but 6n² + 20n  (n³) .