Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>>>   It's like the computational complexity of algorithms: Since an algorithm
>>> will always be run on a computer with limited resources, techincally speaking
>>> that means that all (terminating) algorithms are O(1).
> 
>> Good thing that's not how O() is defined. :-)
> 
>   I think it is. [...]
> Larger O functions come into play only when the resources are unlimited.

I'm pretty sure O() is defined as some function whose value exceeds the 
measurement of your algorithm as n approaches infinity, with n being the 
size of the input (measured in some particular way). So O(n^2) means some 
measurement of your algorithm will eventually be and stay below k*n^2 as n 
grows without bound.

So if your input isn't unbounded, then O() doesn't make much sense. If your 
input is unbounded, then you have an unlimited amount of resources going 
into the problem, as input is one of your resources. Certainly you can't 
sort an unbounded number of elements without an unbounded amount of resources.

I.e., the way O(n) is usually defined counts "n" in memory, and "n" has to 
grow without bound.  (I.e., O(n) usually assumes "offline" work.)

>   However, it's not at all useful to think of algorithms as running within
> limited resources. That doesn't give us any useful information. Computational
> complexity analysis only gives useful information when assuming that resources
> are unbounded.

Certainly computational complexity analysis gives useful information for 
bounded workloads in the sense that an O(lg n) sort is better than an O(n^2) 
sort[1], even on smaller workloads. It's not really useful to say sorting 10 
million text lines is O(1) because you know you only have 10 million of them.


I think we're still talking silly definitions, tho. We both know what's 
going on here. :-)




[1] Modulo ridiculous constants, of course.

-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message