Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Re: An informal introduction to O(N) notation

by fruiture (Curate)
on Jan 18, 2003 at 12:09 UTC ( #227954=note: print w/replies, xml ) Need Help??

in reply to An informal introduction to O(N) notation

I think it's usefull to have a look at a more formal way of saying what the Big O means after having read this informal orientation. In the end, it's not that hard to understand.

You can express the complexity of an algorithm as a complete function that includes constants (startup cost) and constant factors (for example if you iterate over a list thrice), based on the assumption that all primitve actions (+,-,/,*,assignation,...) cost 1 "step" of time. Let's call this function f(n,m,...) where n,m,... are all the variable factors that influence the problem. How can we now find a function g(n,m,...) so that O(g(n,m,...)) = f(n,m,...)? Simple

f(n,m,...) = O(g(n,m,...)) means that there exists a constant "c", for which c * g(n,m,...) >= f(n,m,...) is true for large enough n,m,...

If you think about this relation it's clear that you can forget all constant factors or constants in your program, because a large enough c will always suffice to make c*g() grow faster. Because O(n^2) = O(n^3) you should always find the smallest g() for which f() = O(g()) is true in order to have a representative function g().

f(n,m,...) = &Omega;(g(n,m,...) means that there is .... c * g(n,m,...) <= f(n,m,...)

This is the lower bound. And finally Θ marks an average "middle":

f(n,m,...) = &Theta;(g(n,m,...)) means that f(n,m,...) = O( g(n,m,...) ) and f(n,m,...) = &Omega;( g(n,m,...) )

Replies are listed 'Best First'.
by dakkar (Hermit) on Mar 25, 2003 at 14:26 UTC


    'Ο' is used for an estimate in excess (it's supposed to be a capital omicron, not an 'oh')

    'Ω' is used for an estimate in defect (o-mega "is bigger" than o-micron)

    'Θ' is used for the actual growth.

    For example: mergesort is Ω(1), Ο(n2), Θ(n log n)

    This is important since it's quite common to know boundaries on the complexity, but not the exact complexity. For example, matrix multiplication is Ω(n2) (you have to generate all the elements), and surely Ο(n3) (there is a naif algorithm with that complexity), but we don't know the exact function.

            dakkar - Mobilis in mobile
      While we're nitpicking: O() defines an upper bound (typically, but not exclusively, on worst case behaviour) Ω() defines a lower bound (again typically, but not exclusively, on best-case behaviour) An algorithm is said to run in Θ(f(n)) if it runs in O(f(n)) and in Ω(f(n)), i.e. the upper and lower bounds are no more than a constant multiple of each other. It is a tighter definition than average-case execution complexity which depends on first defining the properties of an "average" input. I think what you're trying to define above is average-case execution complexity - by definition of the Θ() notation your statement above cannot be true. BTW mergesort is O(n lg n). - Menahem
by theorbtwo (Prior) on Jan 18, 2003 at 21:54 UTC

    Thanks. This was the "more formal, but still readable" defintion of O() that I was looking for.

    Also, BTW, while &Theta() is defined as the average-case, I think the normal-case is more often actualy used -- the average case can be impossible (or at least, impraticle) to compute. (Then again, I don't really know what I'm talking about.)


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://227954]
and the pool shimmers...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (3)
As of 2017-12-15 22:53 GMT
Find Nodes?
    Voting Booth?
    What programming language do you hate the most?

    Results (443 votes). Check out past polls.