exponential time complexity for $M(n,n)$ with $ M(i,j) = M(i-1,j) + M(i-1,j-1) + M(i,j-1) $. For $n \in \mathbb{N}$ we define $Q(n) = M(n,n)$ with:
$$ M(i,j) = M(i-1,j) + M(i-1,j-1) + M(i,j-1) $$ and
$$ M(i,0) := M(0,i) := i \mbox{ } \mbox{ } \forall i \geq 0 $$
Show that $Q(n)$ (regarding the recursion above ) does take exponential time complexity. Moreover show that there is an algorithm, which does take quadratic time.
My thoughts:
Regarding the first question I think I understand the problem. I choose $ n = 2 $ and consider the recursion represented as a tree. The subproblems overlap several times. ( not like Mergesort, where the subproblems are disjoint). For example we have to compute $M(1,1)$ three times for $n=2$. So this would be the reason for exponential time complexity, I guess.
For the second question I would say that we can replace the "top-down" strategy of the recursion with a "bottom-up"  strategy. So we start with a subproblem of a "trivial size" and begin to focus of "greater" subproblems. We can note every result in table and use them if we need them for greater subproblems.
That were my thoughts for the two questions.


 for all $j=1:n$ :

    compute all the elements of column $j$ 

   (taking into account the already computed column $j-1$)


gives you a $O(n^2)$ procedure (because each column is processed in $O(n)$ time and there are $n$ columns).
