Base cases: $T(0) = T(1) = a, T(2) = b$. How did we get these base cases? Well, from the code:
if len(lst) <= 1:
return
This tells us that for n < 2
, T
doesn't depend on the input list size; hence, the function takes some constant amount of time for these input sizes.
if lst[0] > lst[-1]:
...
if len(lst) >= 3:
...
This part tells us that for input sizes between 1
and 3
, exclusive (i.e., for 2
) we do some more work than in the n <= 1
case but not as much as in the n >= 3
case. THe amount of work done still doesn't depend on the input size, so it's constant, but it might be difference from that of the n <= 1
case.
Now we consider the n >= 3
case.
Recursive part: $T(n) = 3T(\frac{2}{3}n) + c$. Notice that the three recursive calls each use a list two thirds the size of the input list. To see this, let's consider the code:
if len(list) >= 3:
split = len(lst) // 3
do_something(lst[0..len(lst) - split - 1])
do_something(lst[split..len(lst) - 1]
do_something(lst[0..len(lst) - split - 1])
First off, we see that split
will be equal to one third the length of the input list, rounded down (we assume //
means integer division). We then have three recursive function invocations. To get the input size for these recursive calls, we have to see how big the lists we're passing are. All three are slices of the original input list; we can determine the size of the lists being passed to recursive calls by computing the indices used to determine slices. Observations:
- The first and third slices use the same indices.
0 .. len(lst) - 1
is the entire list, size n
.
split
is one third the list size, equal to n/3
.
- The second slice uses
split .. len(lst) - 1
; to get the size of this slice, we can use simple subtraction of the size of the smaller interval (0..split
) from the bigger interval (0..len(lst) - 1
): n - n/3 = 2/3 n
.
- The first and third slices work similarly: if we take a slice of size
n
and stop it n/3
indices earlier, we get n - n/3 = 2/3 n
.
Now that you have a recurrence relation, you can resolve it using any of a several of techniques.