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

David Van Horn wrote:
> On 9/13/10 2:46 PM, Stephen Bloch wrote:
>> On Sep 13, 2010, at 1:34 PM, Phil Bewig 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.
> 
> Doesn't it make n decisions?  1 decision for each element (the decision 
> being, where does the element go in the shuffled list)?
> 
>    http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

I think the discrepancy comes from the fact that each of those decisions 
takes O(log n) bits, but we customarily pretend that "indexes" are O(1).

Is this right? Does complexity analysis have a notation for 
distinguishing "true" complexity from "for up to k bits" complexity?

Ryan