Analyze Algorithm 3.10, and show its time complexity using order notation.

The following algorithm constructs a binary tree from the array R. Recall that R contains the indices of the keys chosen for the root at each step.

Algorithm 3.9 Optimal Binary Search Tree Problem: Determine an optimal binary search tree for a set of keys, each with a given probability of being the search key. Inputs: n, the number of keys, and an array of real numbers p indexed from 1 to n, where p [i] is the probability of searching for the ith key. Outputs: A variable minavg, whose value is the average search time for an optimal binary search tree; and a two-dimensional array R from which an optimal tree can be constructed. R has its rows indexed from 1 to n+1 and its columns indexed from 0 to n. R[i] [j] is the index of the key in the root of an optimal tree containing the ith through the jth keys. void optsearchtree (int n, const float pll float & minang, index R[](1) index i, j, k, diagonal; float A[1.. n + 110..n]: for (i = 1; i key = Key[k]; p-> left = tree (i, k-1); p-> right = tree (k + 1, j); return p