13. The following algorithm receives as input an array A storing n different integer values Algorithm foo(A, n) Input: Array A storing n different integer values. for i2 ton- 1 do tAli while (j 2 0) and (Aj]> t) do { What is the complexity of this algorithm in the worst case and in the best case? (A) Worst case: O(n) and best case O(n) (B) Worst case: O(n2) and best case O(n) (C) Worst case: O(n3) and best case O(n) (D) Worst case: O(n2) and best case O(n2) (E) Worst case: O((n - 2)t) and best case O(n) 14. Consider the following algorithm. Algorithm rec(n) Input: Integer value n2 0 if n 0 then return 1 else For i ? 0 to n _ I do k ? k + rec(n-1) return Ak Let ci be the number of operations performed when n 0, let c be the number of operations performed outside the for loop when n > 0, and let cs be the number of operations performed in one iteration of the for loop ignoring the recursive calls; c1, o2, and c are constants. What recurrence equation describes the time complexity of the above algorithm in the worst case? (A) f(0) = cl (B) f(o) c (C) f(0) = q (D) f(o) (E) f(0) = q f (n) 2 cn+f(n - 1 + f(n - 2).+f(0), for n >0 f (n) c2 +c3n +nf(n - 1), for n > 0 f (n) c2 +can +f(n 1), for n > 0 f(n) c2 +can +esf(n 1), for n>0 f (n) c2 (n -1)f (n - 1), for n > 0