The OPTIMAL-BST procedure takes   ɵ (n3)  time, just like MATRIX-CHAINORDER.We can easily see that its running time is O(n3), since its for loops are nested three deep and each loop index takes on at most n values. The loop indices in OPTIMAL-BST do not have exactly the same bounds as those in MATRIX-CHAINORDER, but they are within at most 1 in all directions. Thus, like MATRIX-CHAINORDER, the OPTIMAL-BST procedure takes Ω (n3) time.

In general, the running time of (MATRIX-CHAINORDER, the OPTIMAL-BST) is  ɵ (n3)

Best,

Reem