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
Post a Comment