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

Popular posts from this blog

IF statement in MySQL trigger -

c++ - What does MSC in "// appease MSC" comments mean? -

javascript - Blogger related post gadget image Resize s72-c [ Need Expert Help ] -