Recall that the total time to execute the dynamic programming algorithm to compu
ID: 3810618 • Letter: R
Question
Recall that the total time to execute the dynamic programming algorithm to compute an Optimal Static Binary Search tree shape is given by the expression:
Total Time = Time to fill in all diagonals
= sum(k = 1 to n) ( (number of entries in kth diagonal) *
(time to compute the value of one cell in the kth diagonal) )
= sum(k = 1 to n) ( (n + 1 - k) * k )
Show that the expression above simplifies O(n3). Show all of your work. Show each step in your derivation. You may use the identity that
sum(k = 1 to n) ( k2 ) = ( n (n+1) (2n+1) ) / 6
Explanation / Answer
sum(k = 1 to n) ( (n + 1 - k) * k )
= sum(k = 1 to n) (n*k +k - k*k)
= sum(k = 1 to n) (n*k +k) - sum(k = 1 to n) (k*k)
= (c1)sum(k = 1 to n) (k) + (c2)sum(k = 1 to n) (k*k)
where c1 = n+1and c2 = -1
=c1 *(( n)(n+1)/2) +c2 * ( ( n (n+1) (2n+1) ) / 6)
= q1 * n^3 + q2 * n^2 + q3 * n + q4
where q1,q2,q3,q4 are some constants
= q1 * n^3 + q2 * n^2 + q3 * n + q4
As n grows larger n^2,n can be neglected compared to n^3
hence it is of order BigO(n^3)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.