Analysis of recursive algorithm. Consider the pseudocode of the following two algorithms. The input A is an array of size n. In Algl, A is divided into two subarrays, and the algorithm is recursively applied to only one subarray. In Alg2, A is divided into five subarrays, and the algorithm is recursively applied to two or three of them, depending on values in A. Assume that parameter passing takes constant time.

Algi (A[1..n])
if (n <= 1) return;
mid = floor (n/2);
x = rand(); // 0 < x < 1
if (x <= 0.5)
Alg1 (A[1..mid]);
else
Algi (A[mid+1..n]);
end
end

Alg2 (A[1..n])
if (n <= 1) return;
s = floor (n/5);
x = rand(); // 0 < x < 1
if (x <= 0.5)
Alg2 (A[1..s]);
Alg2 (A[s+1..28]);
else
Alg2 (A [2s+1..3s]);
Alg2 (A[38+1..4s]);
Alg2 (A[4s+1..n]);
end
end

What is the worst-case running time of Alg1? What about best-case and average case?