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.

	Space	Time
CutRod(p,n)
MemoizedCutRod(p,n,r)
BottomUpCutRod(p,n)
ExtendedBottomUpCutRod(p,n)

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]