Given the following algorithm, use the master method to find the runtime of the algorithm within a polylog factor of the exact runtime. Then create a recursion tree in order to create a more accurate guess of what the exact runtime should be. Finally use the substitution method to prove that your guess is correct.

Alg(A, n)

1. if n 3

2. return array

3. for i = 0 to n

4. A[i] = A[n i]

5. return Alg(A[1 ... n], n)Alg(A[n + 1 ... 2n], n)Alg(A[2n + 1 ... n], n)