[racket] [BULK] Re: Looking for feedback on code style

On 9/13/10 2:46 PM, Stephen Bloch wrote:

>> Do you know a better way to shuffle a list than to convert it to a
>> vector, shuffle in place, then convert back to a list? You might look
>> at this discussion:
>> http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec.
>> The list-vector-list method is O(n); any functional method appears to
>> be O(n log n).
>
> In fact, ANY method to do this (even with a vector) takes Omega(n log n)
> time. It needs to be able to produce any of n! different answers, so it
> needs to make at least log(n!) decisions, which is Theta(n log n).
> Otherwise there wouldn't be enough leaves on the decision tree.

Sure, in a decision-tree model. But the computational model of Scheme 
isn't that restrictive. Indexing into a vector takes O(1) time and can 
be used to replace a decision tree with n leaves.

One of the things that irritates me about a conventional algorithms 
course is that the underlying model is so fuzzy. When we talk about an 
input of size n, we are really assuming a RAM model with word size c log 
n for some constant c big enough to implement our algorithm without too 
much pain, even though no real machine has an arbitrarily expandable 
word size. And we're not very clear, in these days of powerful languages 
with powerful libraries, about what exactly can be assumed to take O(1) 
time. --PR