[deleted]
Re:How to multiply polynomials in Θ(n log n) time
by thaumasiotes on Monday September 07, 2015 @07:08PM
(#10183423)
This is completely wrong. Big-theta does mean it's an upper bound, and also a lower bound. It certainly does not mean it's the exact number of steps; for example, 5x = Θ(3x), but 5x is more than 3x for all positive x.
Re:How to multiply polynomials in Θ(n log n) time
by dastbe on Monday September 07, 2015 @11:00PM
(#10183981)
Since the parent removed their comment, the gist was that they described f being big-theta of g as f growing exactly as fast as g. this is stricter than what big-theta actually means and is actually defined as "on the order of" or in notation as f ~ g.