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

-- dakkar - Mobilis in mobile

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 |

In Section
Meditations

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