0
$\begingroup$

1)
I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about 100 or 1000 elements? How do I determine recursion tree depth for them? Is there any pattern that I cannot see? What if someone would ask me for recursion tree depth for a string composed of one million elements?

2)
I need to determine the biggest and the smallest recursion tree depth for strings composed of 10, 100 and 1000 when using quicksort. So it's kind of similar but those could be any strings, so is there even constant number that defines the smallest and the biggest? How to count this?

3)
I need to provide a recursive dependency which value for the given $n$ is the number of recursion tree levels of recursive calls of merge sort for an $n$-element string.

Improve this question
$\endgroup$
1
  • $\begingroup$ Start with completely unsorted strings of length 4 and work upto 10. Observe if there are any patterns between the number of recursion tree levels and the number of characters in the string. Extend this pattern for strings of 11 characters. You will get a general formula. $\endgroup$
    – Sagnik
    Commented Jan 22, 2019 at 16:51

2 Answers 2

Reset to default
1
$\begingroup$

  1. There is a pattern, and it has to do with the fact that you are splitting the lists in half in each time. Keep in mind the runtime of mergesort is $O(n \cdot log(n))$, that should provide some hints as to where to go with this problem.

  2. There isn't really a even constant unless you define the constant in terms of $n$. I wouldn't think about this problem in that way, instead I would consider the best and worst cases for quicksort, i.e what choice of pivot is the best / worst, and how does it affect the depth of the recursion tree?

  3. This is very similar to the first problem, in fact, I believe if you figure out the first problem, then this one shouldn't be too hard to come up with. Once again, think about the fact that you are halving the size of the list each time. I'm not sure if you are familiar with recurrence relations, and if not that is something you will definitely want to take a look at.

Here is a good resources to look at:

The whole chapter will be a good read, but for your purposes, just the bits about mergesort and quicksort will suffice

http://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf

I have only given hints and general guidance because I think this is a good problem to think about and to test your understanding of general algorithm analysis, but if you need a stronger hint, feel free to comment.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks, about merge sort, I have those recursive dependencies: T(1) = 0, and for n>1 where n is a even number it's T(n) = T(n/2) + 1, but I have troubles determining the T(n) for odd numbers. And when I have that points 1 and 3 will be sone done, But this one thing I cannot do. so T(1) = 0, T(2) = 1, T(3) = 2, T(4) = 2, T(5), T(6), T(7), T(8) = 3, T(9), T(10), T(11) = 4, T(12) = 5. $\endgroup$
    – Karol
    Commented Jan 22, 2019 at 18:05
  • 1
    $\begingroup$ Close, but your recurrence should be $T(n) = T(\lceil\frac{n}{2}\rceil) + T(\lfloor\frac{n}{2}\rfloor) + O(n)$. The floor and ceiling take care of the even and odd parity issue. The reason there are 2 $T(\frac{n}{2})$, is because you split the array in half, but recurse on both sides. $\endgroup$
    – Shovik Guha
    Commented Jan 23, 2019 at 5:47
0
$\begingroup$

Hint:

About MergeSort:

$$1000=500+500\\ 500 = 250+250\\ 250=125+125\\ 125=63+62\\ 63=32+31\\ 32=16+16\\ 16=8+8\\ 8=4+4\\ 4=2+2\\ 2=1+1$$

Do you understand the pattern ?

Improve this answer
$\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.