0
$\begingroup$

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

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

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).

$\endgroup$
3
  • $\begingroup$ Could you explain why it's okay to ignore the -1 in T((n/2) -1) and simplify it to T(n/2)? $\endgroup$ – user129359 Dec 9 '20 at 0:02
  • $\begingroup$ 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 $\endgroup$ – phan801 Dec 9 '20 at 0:07
  • $\begingroup$ 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. $\endgroup$ – user129359 Dec 9 '20 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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