Finding recursion for runtime of code [duplicate]

Question

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:

Answer 1

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.

Answer 2

Hint: As you mention, there are two cases to consider, the list has length at most 2, and the list has length at least 3. In the first case, only some constant-time statements are executed. In the second case, there are additionally three recursive calls.

Now denote the time it takes to run the algorithm on a list of length $n$ by $T(n)$. (More accurately, $T(n)$ is going to be an upper bound on the running time, since we are not going to consider the cases $n=1$ and $n=2$ separately even though the running times are slightly different; this is OK since we don't care about constants.) The form of the recurrence is $$ T(n) = \begin{cases} ? & \text{if }n \leq 2, \\ T(?) + T(?) + T(?) + ? & \text{if }n \geq 3. \end{cases} $$ Make sure that you understand why this is the form of the recurrence, and then fill in the blanks.