This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: fix opt/8634
> Date: Wed, 9 Apr 2003 06:31:01 +0200 (CEST)
> From: Gerald Pfeifer <pfeifer at dbai dot tuwien dot ac dot at>
> Cc: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>, gcc-patches at gcc dot gnu dot org
> X-OriginalArrivalTime: 09 Apr 2003 04:30:41.0093 (UTC) FILETIME=[C718DF50:01C2FE50]
>
> On Tue, 8 Apr 2003, Geoff Keating wrote:
> > If you take a linear operation (that is, O(n)), and then you perform
> > it K*n times for some fixed constant K, then the program is O(n*n),
> > which is quadratic.
>
> Sorry, but this is certainly not how big-O notation is supposed to work:
> O(K·n) = O(n) for any fixed K > 0, by definition.
Yes. However, K * n * O(n) is O(n*n).
--
- Geoffrey Keating <geoffk at geoffk dot org>