Finding recursion for runtime of code This is the first time we have to do recursive/closed form expressions WITH code in class and I really have no idea how to approach this. My course notes that the prof put up don't really help as he put up a basic example, but this one has lots of recursive calls in it.

I know that the first part len(lst)$ \leq 1$ will be linear time because of it will just return whatever in the conditional. How do I tackle the rest, and ultimately come up with the recursive $T(n)$? The question is below:
Base cases: $T(0) = T(1) = a, T(2) = b$. How did we get these base cases? Well, from the code:

if len(lst) &lt;= 1:
    return


This tells us that for n &lt; 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] &gt; lst[-1]:
    ...

if len(lst) &gt;= 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 &lt;= 1 case but not as much as in the n &gt;= 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 &lt;= 1 case.

Now we consider the n &gt;= 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) &gt;= 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.