int max(int[] array, int first, int last) { if (first == last) return array[firs

ID: 440399 • Letter: I

Question

int max(int[] array, int first, int last) { if (first == last) return array[first]; else if (first + 1 == last) return max(array[first], array[last]); else { int mid = (first + last) / 2; return max(max(array, first, mid), max(array, mid + 1, last)); } } int max(int left, int right) { if (left > right) return left; return right; } 1. Write the recurrence equation that expresses the execution time cost for the above algorithm. Draw the recursion tree assuming that n = 8. 2. Determine the critical exponent for the recurrence equation in problem 3 Apply the Little Master Theorem to solve that equation. Is this algorithm optimal? Explain.

Explanation / Answer

Refer
http://homepages.ius.edu/RWISMAN/C455/html/notes/Chapter4/RecursionTree.htm

It explains how to draw a recursion tree

Use recursion tree to determine a good asymptotic bound on the recurrence T(n) = …

Sum the costs within each level of the tree to obtain a set of per-level costs.

Sum all the per-level costs to determine the total cost of all levels of recursion.
Best if used to generate a good guess for the closed form bounds of the recurrence T(n).
Guess is verified by using Substitution Method or Master Method.

Note: the bound sought will be one of the following:

“asymptotic upper bound” means you’re looking for Big-O
“tight asymptotic bound” means you’re looking for
“asymptotic lower bound” means you’re looking for
Steps:

Draw the tree based on the recurrence

From the tree determine:

# of levels in the tree

cost per level

# of nodes in the last level

cost of the last level (which is based on the number found in 2c)

Write down the summation using notation – this summation sums up the cost of all the levels in the recursion tree

Recognize the sum or look for a closed form solution for the summation created in 3). Use Appendix A.

Apply that closed form solution to your summation coming up with your “guess” in terms of Big-O, or , or (depending on which type of asymptotic bound is being sought).

Then use Substitution Method or Master Method to prove that the bound is correct.

Navigate

int match(const char *s, const char *p, int overlap) { int c = 0; int a=strlen(p

int middle, first_index = 0, last_index = size -1,pos = -1; bool found = false;

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

int max(int[] array, int first, int last) { if (first == last) return array[firs

Question

Explanation / Answer

Related Questions

Navigate