note
dakkar
<p>Nitpicking:</p>
<p>'Ο' is used for an estimate in excess (it's supposed to be a capital omicron, not an 'oh')</p>
<p>'Ω' is used for an estimate in defect (o-mega "is bigger" than o-micron)</p>
<p>'Θ' is used for the actual growth.</p>
<p>For example: mergesort is Ω(1), Ο(n<sup>2</sup>), Θ(n log n)</p>
<p>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<sup>2</sup>) (you have to generate all the elements), and surely Ο(n<sup>3</sup>) (there is a naif algorithm with that complexity), but we don't know the exact function.</p>
<pre>--
dakkar - Mobilis in mobile
</pre>
227909
227954