<p>Binary Representation (Recursively):<br />-----------------------------------
ID: 3625519 • Letter: #
Question
<p>Binary Representation (Recursively):<br />--------------------------------------------<br /><br />if n = 1 return 1<br /><br />else return Binary Representation<img src="https://s3.amazonaws.com/answer-board-image/cramster-equation-20114252211276343936628728161851350.gif" alt="" align="absmiddle" /> + 1</p><p>Questions:</p>
<p>1. What is the principal data structure?</p>
<p>2. What is the input size?</p>
<p>3. What is the fundamental operation?</p>
<p>4. If necessary, compute the best case, worst case, average case.</p>
<p>5. Set up a recurrence relation and include the initial condition(s) to express the number of times the fundamental operation is executed.</p>
<p>6. Solve the recurrence relation and give the order of growth of its solution.</p>
<p> </p>
Explanation / Answer
Analyzing Recursive Algorithms! A recursive algorithm can often be described by a recurrence equation that describes the overall runtime on a problem of size n in terms of the runtime on smaller inputs. For divide-and-conquer algorithms, we get recurrences like: T(n) = !(1) if n " c aT(n/b) + D(n) + C(n) otherwise •! a = number of subproblems we divide the problem into •! n/b = size of the subproblems (in terms of n) •! D(n) = time to divide the size n problem into subproblems •! C(n) = time to combine the subproblem solutions to get the answer for the problem of size n where Analyzing Recursive Algorithms! For recursive algorithms such as computing the factorial of n, we get an expression like the following: T(n) = 1! if n = 0 T(n-1) + D(n) + C(n) otherwise •! n-1 = size of the subproblems (in terms of n) •! D(n) = time to divide the size n problem into subproblems (O(1)) •! C(n) = time to combine the subproblem solutions to get the answer for the problem of size n (O(1)) where
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.