Slices time complexity

[Mario Figueiredo]

On Wed, 20 May 2015 21:47:46 +0100, Mark Lawrence
<breamoreboy at yahoo.co.uk> wrote:

>Please provide the figures to back up this claim.  Nothing personal but 
>we've had problems with the RUE (amongst others) making nonsensical 
>claims, please don't take us down that path, thank you.

Alright. My apologies. This answer of yours along with Ian's made me
realize something was wrong with my measurements. And it was indeed.
Thankfully not the code which I show below. But the fact I wasn't
aware -- until you guys forced me to dig in what was going on -- that
timeit.timeit defaults to 1 million passes.

>#!/usr/bin/env python3
> 
>import random
>import timeit
> 
>def minimum(values):
>    if len(values) == 1:
>        return values[0]
>    else:
>        m = minimum(values[1:])
>        return m if m < values[0] else values[0]
> 
>a5 = [random.randint(0, 1000) for _ in range(5)]
>a50 = [random.randint(0, 1000) for _ in range(50)]
>a500 = [random.randint(0, 1000) for _ in range(500)]
> 
>setup = 'from __main__ import minimum, a5, a50, a500'
> 
>print('Baseline: {:.2f}s'.format(timeit.timeit('minimum(a5)', setup=setup)))
>print('x10  -> {:.2f}s'.format(timeit.timeit('minimum(a50)', setup=setup)))
>print('x100 -> {:.2f}s'.format(timeit.timeit('minimum(a500)', setup=setup)))

One run output is:
   
   Baseline: 2.86s
   x10  -> 36.72s
   x100 -> 1021.07s

Which, as you can see, I misinterpreted as being the result of a
single pass.

The performance was shocking. And I was going to get to that on
another thread. The slice linear time alone couldn't explain it. But
looking more carefully at the documentation revealed my error.