Question

What is the worst-case asymptotic time complexity of the following divide-andconquer algorithm (give a Θ-bound). The input is an array A of size n. You may assume that n is a power of 2.

(NOTE: It doesn’t matter what the algorithm does, just analyze its complexity).

Assume that the non-recursive function call, bar(A1,A2,A3,n) has cost 3n.

Show your work! Next to each statement show its cost when the algorithm is executed on an imput of size n abd give the expression for the run time and derive its complexity in term of Θ.

foo(n,A){

if (n == 1)

return A[0]

Let A1,A2,A3 to be of size n/2

for ( i=0; i<=n/2-1; i++) {

A1[i] = A[i];

A2[i] = A[n/2+i]

   A3[i] = A[2i];

bar(A1,A2,A3,n);

}

x = foo(n/2,A1);

y = foo(n/2,A2);

z = foo(n/2,A3);

return (x+y)*z;

}

Answer 1