0
$\begingroup$

Okay so we've been given an algorithm and asked to give an upper bound to its best and worst case

weirdSort(A,r,p)

if r < p

q = (r+p)/2
BubbleSort(A,r,q)
wierdSort(A,q+1,p)
Merge(A,r,q,p)

I'm not quiet sure how to do that.. this is my first time analysing time complexity and I'm quiet lost

I know that an upper bound for BubbleSort is $O(n^{2})$ for worst and $O(n)$ for best, and for Merge is $O(n)$ for both (Merge being the function that merges the arrays in MergeSort)

So for the worst case I have

$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n^{2}\right)+O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c_{1}n^{2}+c_{2}n$

and for the best case

$T\left(n\right)=T\left(\frac{n}{2}\right)+2O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c_{1}n$

But now what? how do I handle $T\left(\frac{n}{2}\right)$? What are the steps I need to take in these types of questions? I feel like they've just thrown us in the water without really explaining how to solve stuff..

$\endgroup$

2 Answers 2

1
$\begingroup$

Try to find an explicit formula for $T(n)$: Start by writing a few examples, such as $T(2)$, $T(4)$, etc.

Then, after you got some intuition on how $T(n)$ behaves, formulate it as a summation, and find a closed form for it. I will give the example of how to do it for the "best case" scenario:

Examples

$T(2) = T(1) + c_1 \cdot 2$

$T(4) = T(2) + c_1 \cdot 4 = T(1) + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (4 + 2)$

$T(8) = T(4) + c_1 \cdot 8 = T(1) + c_1 \cdot 8 + c_1 \cdot 4 + c_1 \cdot 2 = T(1) + c_1 \cdot (8+4+2)$

Opening recursion

And now (try for yourself) you can prove using induction that:

$T(n) = T(1) + c_1 \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{n}{2^k}$

Finding closed form

Notice that $\sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} = \frac{\left(\frac{1}{2}\right)^{\lfloor \log(n) \rfloor} - 1}{\frac{1}{2}-1} = \frac{1 - \frac{1}{n}}{\frac{1}{2}} \le 2$ Since it is the sum of a geometric progression.

Therefore, $T(n) = T(1) + c_1 \cdot n \cdot \sum_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} \le T(1) + c_1 \cdot 2 \cdot n = O(n)$

$\endgroup$
4
  • 1
    $\begingroup$ Perfect. Exactly what I was looking for. :) Thanks you so much! $\endgroup$ Apr 26, 2021 at 9:22
  • $\begingroup$ Hey why are is it 1/2^k * n and not just sigma 2^k? I don't get that part $\endgroup$ Apr 26, 2021 at 12:28
  • 1
    $\begingroup$ At the first iteration of "unrolling" the recurrence, we get $n$, at the second iteration, another $n/2$, at the third, $n/4$, and at the $k$'th we get an additional $n/2^k$ $\endgroup$
    – nir shahar
    Apr 26, 2021 at 12:39
  • $\begingroup$ Okay I guess I have to go over it a bit more. Regarding the induction, I was literally trying to prove it for 2-3 hours and I'm not even sure I'm trying to prove the correct thing.. can you elaborate a bit more on that step? $\endgroup$ Apr 27, 2021 at 10:56
1
$\begingroup$

I think you've already done most of the work. Now it's just solving the recurrences $$T(n)=T(\frac{n}{2})+O(n)$$ and $$T(n)=T(\frac{n}{2})+O(n^2)$$ Both are pretty straightforward. The key is to keep substituting until you find a pattern, after which you analyze what will happen when the recursion bottoms out. There are 2 common methods, namely the recursion tree method, and the substitution method. The former is more diagrammatic, while the latter involves more algebra.

Here is a great video that solves your first recurrence (best case) while explaining both methods in detail.

Your second recurrence (worst case) has solutions here

For more insight, here are some great lecture notes on solving recurrences.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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