Complexity classes examples -


i wanted know if answers indeed correct following statements:

3(n^3) + 5(n^2) + 25n + 10 = bigomega(n^3) -> t ->grows @ rate equals or slower

3(n^3) + 5(n^2) + 25n + 10 = theta(n^3) -> t -grows @ rate equals

3(n^3) + 5(n^2) + 25n + 10 = bigo(n^3) -> t -grows @ rate equals or faster

thanks!!!

formal definitions of o notations are:

f(n) = o(g(n)) means there exists constant c , n0 f(n) <= c*g(n) n >= n0.

f(n) = Ω(g(n)) means there exists constant c , n0 f(n) >= c*g(n) n >= n0.

f(n) = Θ(g(n)) means there exists constants c1 , c2 , n0 f(n) >= c1*g(n) , f(n) <= c2*g(n) n >= n0.

proof o:

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

you can see n >= 10 formula true. there exists c = 5 , n0 = 10, o(n^3).

proof Ω:

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

so c = 3 , n0 = 1, Ω(n^3).

because both o , Ω apply 3rd statement Θ true.


Comments

Popular posts from this blog

android - MPAndroidChart - How to add Annotations or images to the chart -

javascript - Add class to another page attribute using URL id - Jquery -

firefox - Where is 'webgl.osmesalib' parameter? -