Slices time complexity

[Ian Kelly]

On Wed, May 20, 2015 at 1:51 PM, Mario Figueiredo <marfig at gmail.com> wrote:
> On Wed, 20 May 2015 03:07:03 +1000, Steven D'Aprano
> <steve+comp.lang.python at pearwood.info> wrote:
>
>>Yes, a slice can be expensive, if you have (say) a ten billion element list,
>>and take a slice list[1:].
>
> Since nothing seems to surprise you and you seem so adamant on calling
> anyone being surprised by it, maybe I will surprise you if you
> actually run the code I posted on the OP and witness for yourself that
> even on a 50 element list will take 3 seconds to execute on an intel
> i5.

I suspect you've made a mistake in your timing. I measure it at 20.8
microseconds on a Xeon W3690.

>>> def minimum(values):
...     if len(values) == 1:
...         return values[0]
...     else:
...         m = minimum(values[1:])
...         return m if m < values[0] else values[0]
...
>>> from timeit import Timer
>>> t = Timer("minimum(values)", setup="from __main__ import minimum; values = list(range(50))")
>>> min(t.repeat(number=100000))
2.077940827002749