CODEWITHSUNDEEP
time-complexitycomplexity-theory
idelara
idelara

Reputation: 1816

Complexity classes examples

I wanted to know if my answers are indeed correct for the following statements:

3(n^3) + 5(n^2) + 25n + 10 = BigOmega(n^3) -> T ->Grows at a rate equals or slower

3(n^3) + 5(n^2) + 25n + 10 = Theta(n^3) -> T -Grows at a rate exactly equals

3(n^3) + 5(n^2) + 25n + 10 = BigO(n^3) -> T -Grows at a rate equals or faster

Thanks!!!

Upvotes: 1

Views: 51

Answers (1)

Giorgi Nakeuri
Giorgi Nakeuri

Reputation: 35790

Formal definitions of O notations are:

f(n) = O(g(n)) means that there exists some constant c and n0 that f(n) <= c*g(n) for n >= n0.

f(n) = Ω(g(n)) means that there exists some constant c and n0 that f(n) >= c*g(n) for n >= n0.

f(n) = Θ(g(n)) means that there exists some constants c1 and c2 and n0 that f(n) >= c1*g(n) and f(n) <= c2*g(n) for n >= n0.

Proof for O:

3(n^3) + 5(n^2) + 25n + 10 < 3*n^3 + n^3 + n^3 = 5*n^3

You can see that for n >= 10 this formula is true. So there exists c = 5 and n0 = 10, thus it is O(n^3).

Proof for Ω:

3(n^3) + 5(n^2) + 25n + 10 > 3*n^3

So c = 3 and n0 = 1, thus it is Ω(n^3).

Because both O and Ω apply then the 3rd statement for Θ is also true.

Upvotes: 1

Related Questions