3 Recursions to Recurrence T(n) and Master Theorem

Question

Suppose I have the below code and my task it to find the recurrence T(n) and its worst runtime. The value if n is the length of the list.

In this case, we have 3 recursions, mystery(mylist[:len(mylist)-t-1]), mystery(mylist[t:len(mylist)- 1]) and mystery(mylist[:len(mylist)-t-1]).

def mystery(mylist):
   if len(L) <= 1:
       return
   if len(mylist) >= 3:
       t = len(mylist) // 3
       mystery(mylist[:len(mylist)-t-1])
       mystery(mylist[t:len(mylist)- 1])
       mystery(mylist[:len(mylist)-t-1])

For the recursive case, my observation is because the recursion are together, so the recurrence is:

T(n) = T(floor(2n/3)) + T(floor(n/3)) + T(floor(2n/3)) = 2T(floor(2n/3)) + T(floor(n/3))

Now here is the hard part, to figure out f(n), so I expanded the recursive T(n) and I got more and more T(n)s. How would I be able to figure out f(n)?

For the base case, T(0) and T(1) are 1 because of the first if-statement and T(2) = 0 because there is no if-statement for n=2.

Are my assessments correct?

Thank you!

Answer 1

You are right about the base cases. You could even group T(2) in there. It's still O(1) as you're at least evaluating the two conditional statements, and practically speaking there aren't any O(0) function calls.

The f(n) term in your recurrence is just an expression of all the work you do in the recursive case outside of generating recursive calls. Here you have the O(1) t = len(mylist) // 3 statement and the O(1) cost of evaluating the two conditional statements: O(1) work in total. However, you also have the O(n) cost of slicing your list into three parts to pass into the recursive calls. This gives f(n) = O(n) + O(1) = O(n). From this, we can express the overall recurrence as:

T(n) = 2T(2n/3) + T(n/3) + O(n) if n >=3
T(n) = 1                        otherwise

However, the Master Theorem doesn't apply to this case because you have recursive calls which work on different sub-problem sizes: you can't isolate a single a nor b value to apply the Master Theorem. For a recurrence like this, you could apply the generalization of the Master Theorem known as the Akra-Bazzi Method, with the parameters being:

• a1=2, a2=1
• b1=2/3, b2=1/3
• g(n) = n
• h1(n) = h2(n) = 0

Following the method, solve 2(2/3)^p + (1/3)^p = 1 for p, then evaluate the integral:

with g(u) = u (as g(n) = n) to determine the complexity class.

If you don't need the exact complexity class, but only want to derive a more simple upper-bound with the Master Theorem, you could upper-bound your recurrence relation for the run-time using the fact that 3T(2n/3) >= 2T(2n/3) + T(n/3):

T(n) <= 3T(2n/3) + O(n) if n >=3
T(n)  = 1               otherwise

Then, you can solve this upper bound on the time-complexity with the Master Theorem, with a=3, b=3/2, and f(n)= n^c = n^1 to derive a Big-O (rather than Big-Theta) complexity class.