Consider the following algorithm:

• AlgorithmFoo(int a[], int n):

• Input: an array of integersa, andnis the length of the array

• Output: ?

• If n<0 then show out of bound exception.

• If n == 0 then

  • Return a[n];

• Else

  • Return (a[n] * Foo(a, n-1))

What does this algorithm do? Analyze its worst-case running time, and express it using "Big O" notation.