Answer to Question #199002 in Algorithms for Emre

Question

PRINT-OPTIMAL-PARENS(s, i, j){

if (i=j) then

print “A”i else{

print “(”

PRINT-OPTIMAL-PARENS(s,i,s[i, j])

PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j)

print “)”} }

b- Find the complexity of your program?

c- Show that the parenthesization algorithm is loop invariant?

Answer 1

b)

The time complexity of the algorithm $O(n^3)$