Time Complexity of CLRS Optimal Parenthesis Algorithm

asymptoticscomputer sciencerecursive algorithms

I am reading the Introduction to Algorithms CLRS book, and I am unsure about the time complexity of one of the algorithms that is a recursive algorithm that calls itself twice. This chain matrix multiplication algorithm has an accompany algorithm below it which is what I would like to find an upper bound for.

This one below is the one I would like to find the upper bound. It displays the optimal chain matrix multiplication with parenthesis:

I would like to know the upper bound time compexity of PRINT-OPTIMAL-PARENS where the input $n$ signifies the number of matrices given. I drew out a recursion tree for $5$ matrices and noticed it looks similar to divide and conquer where the first $3$ levels are full and the last $4$th level has $2$ more calls, giving a total of $9$ calls. But the number of calls can't be $O(n \log_2 n)$ like a divide and conquer merge sort since each call does $O(1)$ work and the problem isn't being divided. Which made me think that the function has no possible way going above the number of elements of $s$, $|s|$, where I could use that as the upper bound.

$$
|s| = O\left({n \choose 2}\right) = O\left(\frac{n(n-1)}{2}\right) = O(n^2)
$$

Is this correct? It looks wrong to me since this algorithm doesn't look $O(n^2)$.

Best Answer

Each call to Print() prints either one matrix name, or pair of parentheses. In output there are $n$ matrix names and $n - 1$ pairs of parentheses. Therefore there will be at most $2n - 1$ calls to Print().

Related Solutions

[Math] What will the recursion tree of Fibonacci series look like

What he's doing is using a simple example of what's known as dynamic programming, where one computes a function $f(n)$ by working up from the bottom to get to the desired result. Specifically, to compute $fib(n)$, the $n$-th Fibonacci number, he's doing this

fib(n)=
   if (n <= 1)
      return n
   else
      old = 0, prior = 1, next
      for i = 2 to n
         next = old + prior
         old = prior
         prior = next
      return next

To see this in action, we compute $fib(4)$, which we know is $3$:

i  old  prior  next
2   0     1      1    (compute next = old + prior)
2   1     1      1    (shift everything to the left)
3   1     1      2    (compute next again)
3   1     2      2    (shift again)
4   1     2      3    (and so on...)
4   2     3      3

How long does this algorithm take? No need for the Master Theorem here: we have an algorithm that consists, essentially, of a loop, so assuming you can add in constant time, this will have running time $T(n) = \Theta(n)$.

(Actually, this won't work at all on real machines, since $fib(n)$ grows so fast that the numbers will quickly exceed the size of an integer. For example, $fib(2500)$ is 523 decimal digits long, so we'd need to implement some big integer package to do the addition and assignment statements, increasing the run time of this algorithm.)

The recursion tree for the original (terrible) recursive algorithm looks like this, when computing $fib(4)$:

enter image description here

For example, the first call, to $fib(4)$, requires two recursive calls, to $fib(3)\text{ and }fib(2)$. Notice how inefficient this is: just to compute $fib(4)$ we needed nine function calls. In fact, this is a classic example of when not to use recursion, especially since there are vastly more efficient ways to do this porblem.

[Math] Time complexity of random algorithm

Obviously the time complexity is $\Omega(n)$, because the outer loop runs $n$ times.

Similarly, the time complexity is $O(n^2)$, because the complexity of MultiDecrem is $O(n)$.

Finally, consider that MultiDecrem was called $k$ times. Naturally, decrem helps us, so let's assume that the rest were increm calls and denote their number between $(i-1)$-th and $i$-th MultiDecrem as $a_i$. This gives a bound for the total number of operations that MultiDecrem preforms (modulo missing ceil and floor functions)

\begin{align} (n+a_0)/2+((n+a_0)/2+a_1)/2 + \ldots \leq n + a_0 + a_1 + a_2 + \ldots + a_k \leq 2n \end{align} because $\sum_i a_i \leq n$. Hence, the algorithm is $O(n)$ and so $\Theta(n)$ as well.

I hope this helps $\ddot\smile$

Related Question