Entries Aij Matrix Computed According Formula Aij 1 1 J 1 Aij 0 1 J 1 Aij Ai 1 J Ai J 1 2 Q11261785
The entries aij of matrix A are computed according to theformula aij =1 for i=1, j>1, aij=0 for i>1, j=1, aij =(ai-1,j + ai,j-1)/2 for i>1, j>1.
(i) Estimate the number of operations + that are necessary tocompute aij. Apply dynamic programming approach discussed in class.Provide a justification of your estimate.
(ii) What are the minimal space resources you need for yourcomputation, i.e. how many computed values do you need to keep inorder to be able to compute aij?