Operator O in Physics: Definition & Uses

[pivoxa15]

This operator, captial O is used in physics such as electrodynamics and can be placed in front of functions (i.e. Of(x)). Could someone explain it clearly with a definition. In what situations is it used?

 

[CRGreathouse]

I'm too tired to explain properly. Here's a link:
http://en.wikipedia.org/wiki/Big_O_notation

If you have any questions, just ask.

 

[pivoxa15]

It seems the order (O) of f(x), which is g(x) (or f(x)=O(g(x))) provides the largest order of magnitude of growth for f(x).

Whereas the little order (o) provides f(x) with a function which is one order of magnitude larger than the largest order of growth for f(x). Although I haven't regiorously explained order of magnitude, I had the limit definitions of these functions in mind. Why would they use o to describe a larger function than O?

 

[CRGreathouse]

I don't know the history behind the notation, but I'm sure you could find it if you're really interested.

A function f is O(g(x)) if g(x) is no larger asymptotically. It is o(g(x)) if g(x) is smaller asymptotically.

Small o is useful when you have a function (or algorithm) that grows (runs) faster than one function but slower than another. The best factoring algorithms, for example, are o(2^n) but Ω(n^c). (Ω is just the opposite of o; f is Ω(g(x)) if g(x) is greater asymptotically.)

 

[pivoxa15]

I also realized that
if f(x)=o(g(x)) then f(x)=O(g(x))

 

[CRGreathouse]

Yeah. O is like <=, o like <, Ω like >=. There is also little-omega (>), but that's rare.

 

[0rthodontist]

Asymptotic notation has to do with "within a constant multiple" rather than just strictly greater than or less than. You write
f(n) = O(g(n)) iff there is some N and some k > 0, where for any n >= N, you have 0 <= k * f(n) <= g(n)

One book I have uses f(n) $$\in$$ O(g(n)) instead of f(n) = O(g(n)) to emphasize that O(g(n)) actually is a set of functions that are asymptotically within a constant multiple of each other.

 

[CRGreathouse]

Asymptotic notation has to do with "within a constant multiple" rather than just strictly greater than or less than. You write
f(n) = O(g(n)) iff there is some N and some k > 0, where for any n >= N, you have 0 <= k * f(n) <= g(n)

Yes, of course. That's what I mean when I say "asymptotically less than" and such.

The operator comparisons are good for people just getting used to the notation, as long as they understand the underlying definition. It helps keep people from flipping them by accident (hopefully!).

One book I have uses f(n) $$\in$$ O(g(n)) instead of f(n) = O(g(n)) to emphasize that O(g(n)) actually is a set of functions that are asymptotically within a constant multiple of each other.

I rather prefer that notation. I can't stand to see the = sign abused. In my posts above I only used "f is O(g(x))" rather than "f = O(g(x))" for that reason. Set notation isn't that common, so I didn't want to cause confusion, but I also don't like extreme notation abuse. (I can live with little stuff, but = is fundamental and should be used properly.)

 

[shmoe]

It seems the order (O) of f(x), which is g(x) (or f(x)=O(g(x))) provides the largest order of magnitude of growth for f(x).

It's not the largest order of magnitude of growth, rather an upper bound for the order of the growth. It doesn't need to be optimal in any way, x^2=O(x^34), this is as x->infinity. You will also see this big-O notation with other limit points, like 0 with taylor polynomials, e^x=1+x+O(x^2) just means there is a constant A>0 that in some small enough neighbourhood of x=0 we have |e^x-1-x|<=A|x^2|


About the "=", I don't tend to think of O(f(x)) as meaning a set of functions, rather as a specific function that's bounded by a constant times f(x), and all we really care about is this functions growth is bounded in this way. For example, writing x+cos(x)=x+O(1), the O(1) to me is really standing for the function cos(x) but all that's going to matter later on is that this term is bounded in absolute value by a constant. The convenience is not having to keep exact track of what function is being hidden by the big-O at each step when all you care about are bounds.

there's also the Vinogradov notations of the double arrows $$f\ll g$$ which means the same thing as the landau big-O, f=O(g).

 

[pivoxa15]

It's not the largest order of magnitude of growth, rather an upper bound for the order of the growth. It doesn't need to be optimal in any way, x^2=O(x^34), this is as x->infinity.

With your example, there is no doubt it is correct but o can be used as well and is a better alternative. Because all o can be replaced by O (but not vice versa) so it means it is always best to use o if possible (otherwise what is the point of having o).

There is no doubt O is used more often than o and that could be why Wiki only has one entry called big O, not small o.

 

[CRGreathouse]

With your example, there is no doubt it is correct but o can be used as well and is a better alternative. Because all o can be replaced by O (but not vice versa) so it means it is always best to use o if possible (otherwise what is the point of having o).

There is no doubt O is used more often than o and that could be why Wiki only has one entry called big O, not small o.

Θ is best, if you can use it. f(x) is Θ(g(x)) iff f(x) is O(g(x)) and g(x) is O(f(x)). To extend the above analogy, it's like =.

 

[0rthodontist]

Big-O comes from examining the worst case behavior of an algorithm, but little o doesn't seem to have such an intuitive origin. I guess you could use it to say that one algorithm runs asymptotically better than another, but I haven't seen that used. When you say an algorithm is big-O of a function there's usually the understanding that there are some inputs for which the algorithm is exactly theta of the function--you want to find the smallest possible function that the algorithm is big-O of. If you say an algorithm is little-o of a function then you just want to ask what's the closer bound.