1
$\begingroup$

This question already has an answer here:

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:

enter image description here

|cite|improve this question
$\endgroup$

marked as duplicate by David Richerby, FrankW, D.W.♦, lPlant, R B Oct 15 '14 at 13:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What is it that you want? A recurrence or a closed form? What did you try? Where did you get stuck? $\endgroup$ – David Richerby Oct 11 '14 at 23:52
  • $\begingroup$ I am fine with getting closed form from recurrence. I am just needing help to analyze this code and how to come up with a recurrence relation. $\endgroup$ – jessie123123 Oct 12 '14 at 0:03
  • $\begingroup$ @Jared I, in fact, didn't vote it as a duplicate. My point is that your complaint about other users' opinions is invalid; they should vote their conscience. I have not voted. I am cleaning up Hey Irina, Glad to hear it works! In IE, you only need %23 in the URL bar; in the text box, # is indeed needed. Never tried with Chrome... but some comments here; please take further discussion to Meta or chat. Thanks for your cooperation. $\endgroup$ – Patrick87 Oct 12 '14 at 15:14
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @Patrick87 I really wish I could be as intelligent as and as good of a teacher as you. =) what is your secret $\endgroup$ – jessie123123 Oct 12 '14 at 20:37
  • $\begingroup$ @jessie123123 I'm glad this answer helped you. Like anything, how well you do depends on a combination of talent and practice. In my case, that I'm ever any help at all is attributable to the latter. $\endgroup$ – Patrick87 Oct 12 '14 at 22:37
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer, but why is it $n \leq 2$ rather than 1? $\endgroup$ – jessie123123 Oct 12 '14 at 16:29
  • $\begingroup$ It is $n \leq 2$ since the recursive calls only happen when $n \geq 3$. $\endgroup$ – Yuval Filmus Oct 12 '14 at 20:14
  • $\begingroup$ Your intuition was very helpful too. I appreciate your response =) $\endgroup$ – jessie123123 Oct 12 '14 at 20:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.