Big-O notation

[A. Lloyd Flanagan]

"Andrew Dalke" <adalke at mindspring.com> wrote in message news:<b7kk53$fe7$1 at slb2.atl.mindspring.net>...
> A. Lloyd Flanagan
> > This mathematical analysis of an algorithm's behavior (and best-case,
> > average, and worst-case performance) can be trivial.  For example, x +
> > 1 is O(1).
> 
> Or not so trivial.  If x can be an arbitrary size integer, represented
> in memory as a chunk of bits, the value 'n' for the number of bits,
> and a sign flag, then addition could be O(n) == O(log(x)).  Eg,
> suppose    x =  1111111111111111111111111111111111111111
> add 1 to get = 10000000000000000000000000000000000000000
> so 49 bits were affected.
> 
> But for fixed size integers, the above is true.
> 
>                     Andrew
>                     dalke at dalkescientific.com


I stand corrected.  See, this algorithm-analysis stuff can tricky!