Monday, April 30, 2012

Ideal Skip list ? O(n) run-time?

I'm trying to find the best algorithm for

converting an "ordinary" linked list 
into an `ideal skip list`


Where the definition of an ideal skip list is that in the first level we'll have all
the elements , in the level above - half of them , the one after - quarter of them ... and so on .

I'm thinking about O(n) run-time where involving throwing a coin for each node in
the original linked-list , whether or not for a specific node , should I go up or not , and create another duplicate node for the current node upstairs ...
Eventually this algorithm would produce O(n) , is there any better algorithm ?


No comments:

Post a Comment