4. (16 points) Guess a plausible solution for the complexity of the recursive al

Question

4. (16 points) Guess a plausible solution for the complexity of the recursive algorithm characterized by the recurrence relations un) T(n/2)+T(n/4)+T(n/8)+T(n/8)+n; T(1) c using the Substitution Method. (1) Draw the recursion tree to three levels (levels 0,1and 2) showing (a) all recursive executions at each level, (b) the input size to each recursive execution, (c) work done by each recursive execution other than recursive calls, and (d) the total work done at each level. (2) Pictorially show the shape of the overall tree. (3) Estimate the depth of the tree at its shallowest part. (4) Estimate the depth of the tree at its deepest part. (5) Based on these estimates, come up with a reasonable guess as to the Big-Oh complexity order of this recursive algorithm. Your answer must explicitly show every numbered part described above in order to get credit.

Explanation / Answer

Substitution Method: We make a guess for the solution and then we use mathematical induction to prove the the guess is correct or incorrect.

Recurrence Tree Method: In this method, we draw a recurrence tree and calculate the time taken by every level of tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start from the given recurrence and keep drawing till we find a pattern among levels. The pattern is typically a arithmetic or geometric series.

I will give you the example of the given solution.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.