From: Ragunathan Pattabiraman <ragunathan.pattabiraman@...>
Date: 2008-06-20T00:22:22+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?

Cheers,
Ragu
-- 
Posted via http://www.ruby-forum.com/.