This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]
Other format:	[Raw text]

Re: fix opt/8634

From: Andrew Pinski <pinskia at physics dot uc dot edu>
To: Gerald Pfeifer <pfeifer at dbai dot tuwien dot ac dot at>
Cc: Andrew Pinski <pinskia at physics dot uc dot edu>, Geoff Keating <geoffk at geoffk dot org>, Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>, gcc-patches at gcc dot gnu dot org
Date: Wed, 9 Apr 2003 00:58:24 -0400
Subject: Re: fix opt/8634

But really the math is K*n*O(n) = O(n^2) for any K>0 aka you call the function K*n times, and the function takes O(n) time. So really it is still O(n^2).

Thanks,
Andrew Pinski

On Wednesday, Apr 9, 2003, at 00:31 US/Eastern, Gerald Pfeifer wrote:

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.

Gerald -- Gerald "Jerry" pfeifer at dbai dot tuwien dot ac dot at http://www.pfeifer.com/gerald/

Follow-Ups:
- Re: fix opt/8634
  - From: Gerald Pfeifer

References:
- Re: fix opt/8634
  - From: Gerald Pfeifer

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]