Determine the performance (big-O and ~) and result for abc .. Note: this is pseu

Question

Determine the performance (big-O and ~) and result for abc..

Note: this is pseudo-code – it should be intelligible, but not necessarily compilable or correct.

float[] abc(float[N] p, float[N] q, int N) {

float[N div 2] pl,ql,ph,qh,t1,t2; float[N] rl, rm, rh;

float[2N-1] result; int i, N2;

if (N=1) then

mult[0] = p[0]*q[0];

else {

N2 = N div 2;

for (i=0; i < N2; i++){ pl[i] = p[i];

ql[i]=q[i];

}

for (i=N2; i < N; i++){ ph[i-N2] = p[i];

qh[i-N2] = q[i];

}

for (i=0; i<N2; i++) { t1[i] = pl[i]+ph[i];

t2[i] = ql[i]+qh[i];

}

rm = abc(t1,t2, N2); rl = mult(p1,ql, N2); rh = mult(ph,qh, N2);

result[N-1] = 0;

for (i=0; i<N2; i++){ result[i] = r[i]; result[N+i] = rh[i];

result[N2+i] = = mult[n2+i]+rm[i]-(rl[i]+rh[i]))

}

return result;

}

Explanation / Answer

Here in the else block, there are 4 for loops and each for loops executes based on its conditions. Before going to first for loop, the value of N2 is N/2, so for loops with N2 condition will repeat N/2 times . So first for loop will repeat upto N/2 times. Second for loop from N/2 to N. Third for lop repeat N/2 times and similarly fourth one wit N/2 times. So totally it will execute for 2N times. So the Big O notation will be O(n).

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.