From: Ragunathan Pattabiraman <ragunathan.pattabiraman@...>
Date: 2008-06-20T01:12:30+09:00
Subject: Re: little problem (google hiring puzzle)


>> input[0...index] + input[index+1..-1]
>> 
>> Isn't it basically just iterating over the list and yielding? In which
>> case, your original loop:
> <snip>
>> will be interpreted as having a nested loop inside. So essentially
>> your running time is bound to n^2 - n, which is O(n^2)
> 
> each_index is iterating over and yielding, there we have the first loop. 
> But I am not sure how Ruby Array's [] is implemented when a range is 
> given. I will take a look when I get a chance (again there is JRuby, 
> IronRuby, and the native Ruby).
> 
> But isn't it safe to assume it would have optimized implementation done 
> by Ruby implementors than the ad hoc O(n) implementation?

I checked Ruby 1.8.7 source code and Array[range] is done at constant 
time. Here is the link to array.c 
http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/branches/ruby_1_8_7/array.c?view=markup

-- 
Posted via http://www.ruby-forum.com/.