# Need help with recurrence relation and postcondition of a function

I just wanted to make sure I'm on the right track regarding this.

Here's the function that I'm dealing with:

import math

def Mystery2(A, f, l):
if f == l:
return A[f]
m = math.floor((f+l)/2)
x = Mystery2(A, f, m)
c = 0
i = f
while i <= l:
if A[i] == x:
c = c + 1
i = i + 1
if c > (l-f+1)/2:
return x
return Mystery2(A, m+1, l)


The precondition is given as: A is an array of integers, and $$f$$ and $$l$$ are integers $$0 \leq f \leq l < len(A)$$.

From what I can see by running the function, the postcondition appears to be that it outputs the element within f and l indices that occurs more than $$\frac{l-f+1}{2}$$ times or A[l].

I'm not sure how to find a closed form for the recurrence relation representing the worst case runtime.

So far I figured that with $$T(n)$$ being the worst runtime of the function and $$n = l-f$$, $$T(n)$$ will be constant if $$n = 0$$ and $$T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil - 1) + n*c_1 + c$$, if $$n > 0$$. I'm not sure how to convert this into a closed form.

Is it okay to simplify this into $$T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil) + n*c_1 + c$$ for the purpose of comparing it to the master theorem?

Thanks in advance for any help

• What does c_1 stand for? – phan801 Dec 8 '20 at 22:56
• a constant runtime for the statements within the while loop – user129359 Dec 8 '20 at 23:02

## 1 Answer

Without having checked if $$T(n)$$ is correct, you can find the closed form by:

$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lceil\dfrac{n}{2}\rceil - 1) + n*c_1 + c$$

If n is odd, you can rewrite $$T(n)$$ as:

$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c =$$

$$T(n) = 2T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c$$

If you substitute $$T(\lfloor\dfrac{n}{2}\rfloor)$$ you get

$$T(n) = 2( 2T(\lfloor\dfrac{n}{4}\rfloor) + \dfrac{n}{2}*c_1 + c ) + n*c_1 + c =$$

$$T(n) = 4T(\lfloor\dfrac{n}{4}\rfloor) + 2n*c_1 + 3c$$

If you substitute $$T(\lfloor\dfrac{n}{4}\rfloor)$$ you get

$$T(n) = 4 (2T(\lfloor\dfrac{n}{8}\rfloor) + \dfrac{n}{4}*c_1 + c) + 2n*c_1 + 3c =$$

$$T(n) = 8T(\lfloor\dfrac{n}{8}\rfloor) + 3n*c_1 + 7c$$

Now you can observe the pattern and see that after substituting $$\dfrac{n}{2^{k-1}}$$

$$T(n) = 2^kT(\lfloor\dfrac{n}{2^k}\rfloor) + k*n*c_1 + (2^0 + 2^1 +...+ 2^k)c$$

Let $$n = 2^k$$

$$T(n) = nT(1) + n*log_2n*c_1 + (2^0 + 2^1 +...+ n)c =$$

$$T(n) = n + n*log_2n*c_1 + (2^n - 1)c =$$

$$T(n) = n + n*log_2n*c_1 + 2^n*c - c =$$

So you have $$O(2^n)$$

Now if n is even, you have

$$T(n) = T(\dfrac{n}{2}) + T(\dfrac{n}{2} - 1) + n*c_1 + c$$

And you follow the same method as before (i.e., start by substituting n/2 and find the pattern after a few iterations).

• Could you explain why it's okay to ignore the -1 in T((n/2) -1) and simplify it to T(n/2)? – user129359 Dec 9 '20 at 0:02
• You man in the odd case, right? Because of the ceil and floor functions. For example, let n = 5. floor(5/2) = floor(2.5) = ceil(5/2) - 1 = ceil(2.5) - 1 = 2 – phan801 Dec 9 '20 at 0:07
• Okay makes sense. I don't think I'm able to figure out a nice closed form for the even case because the T() part keeps increasing with each replacement unlike in the odd case. – user129359 Dec 9 '20 at 0:21