Problem 93 Fill in the table below with estimates for the space and time complex
ID: 3811596 • Letter: P
Question
Problem 93 Fill in the table below with estimates for the space and time complexity of the algorithms listed in first column. Justify your answers.
MEMOIZED-CUT-ROD-AUX.p; n; r/ 1
if r[n] >= 0
return r [n]
if n == 0
q = 0
else q = -infinity
for i = 1 to n
q = max(q.p[i] + MEMOIZED-CUT-ROD-AUX (p,n-i,r))
r[n] = q
return q
ExtendedBottomUpCutRod (p,n)
let r[0...n] and s[0..n] be new arrays
r[0] = 0
for j = 1 to n
q = - infinity
for i = 1 to j
if q < p[i] + r[ j - i ]
q = p[i] + r [j - i]
s[j] = i
r[j] = q
return r and s
--------
Cut_Rod(p,n)
if n ==0
return 0
q = -infinity
for i = 1 to n
q = max(q,p[i] + Cut-Rod(p,n-i))
return q
---
Bottom-Up-Cut-Rod(p,n)
let r[0..n] be a new array
r[0] = 0
for j = 1 to n
q = - infinity
for i = 1 to j
q = max(q,p[i] + r[ j - i])
r[j] = q
return r[n]
Space Time CutRod(p,n) MemoizedCutRod(p,n,r) BottomUpCutRod(p,n) ExtendedBottomUpCutRod(p,n)Explanation / Answer
Space Time CutRod(p,n) Depth of recursion N Exponential (2^n) MemoizedCutRod(p,n,r) O(N) + Depth of recursion N O(N) BottomUpCutRod(p,n) O(N) O(N2) ExtendedBottomUpCutRod(p,n) O(2N) O(N2)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.