News for hackers. Stuff that matters.
[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.