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

android - How to save instance state of selected radiobutton on menu -

python 3 IndexError: list index out of range -

IF statement in MySQL trigger -