Re: Re: An informal introduction to O(N) notation

in reply to Re: An informal introduction to O(N) notation
in thread An informal introduction to O(N) notation

Nitpicking:

'Ο' 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), Ο(n²), Θ(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 Ω(n²) (you have to generate all the elements), and surely Ο(n³) (there is a naif algorithm with that complexity), but we don't know the exact function.

-- 
        dakkar - Mobilis in mobile

Comment on Re: Re: An informal introduction to O(N) notation

Replies are listed 'Best First'.
Re^3: An informal introduction to O(N) notation by Anonymous Monk on Aug 29, 2007 at 14:14 UTC
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	[reply]

Replies are listed 'Best First'.

Re^3: An informal introduction to O(N) notation
by Anonymous Monk on Aug 29, 2007 at 14:14 UTC

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

[reply]

In Section Meditations