algorithm - Can you do addition/multiplication with Big O notations? -
i'm taking algorithm class, , we're covering big o notations , such. last time, talked how
o (n^2 + 3n + 5) = o(n^2) and wondering, if same rules apply this:
o(n^2) + o(3n) + o(5) = o(n^2) also, following notations hold ?
o(n^2) + n or
o(n^2) + Θ (3n+5) the later n outside of o, i'm not sure should mean. , in second notation, i'm adding o , Θ .
at least practical purposes, the landau o(...) can viewed function (hence appeal of notation). this function has properties standard operations, example:
o(f(x)) + o(g(x)) = o(f(x) + g(x)) o(f(x)) * o(g(x)) = o(f(x) * g(x)) o(k*f(x)) = o(f(x)) for defined functions f(x) , g(x), , constant k.
thus, examples,
yes: o(n^2) + o(3n) + o(5) = o(n^2)
and:
o(n^2) + n = o(n^2) + o(n) = o(n^2),
o(n^2) + Θ(3n+5) = o(n^2) + o(3n+5) = o(n^2)
Comments
Post a Comment