/* ** compute a[0] + a[1]*x + a[2]*x*x + a[3]*x*x*x ** ... a[degree]*x^degree */ int poly1(int *a, int degree, int x) { int i, j, xp, ret; ret = 0; for (i=0; i<=degree; i++) { xp = 1; for (j=0; j<i; j++) { xp *= x; } ret += a[i]*xp; } return ret; } /* ** compute a[0] + a[1]*x + a[2]*x*x + a[3]*x*x*x ** ... a[degree]*x^degree */ int poly2(int *a, int degree, int x) { int i, j, ret; ret = a[degree]; for (i=degree-1; i>=0; i--) { ret = a[i] + x*ret; } return ret; }

- What is the asymptotic efficiency O(n) for the method implemented in the C function poly1()?
- Briefly describe how inspecting the general structure of the assembly poly1-O0.S and poly1-O3.S allows you to determine O(n) of the assembly without and with optimization. Did the opimizations change it?
- Now consider poly2(), which uses Horner's method and its optimized compilation poly2-O3.S What is the asymptotic efficiency O(n) for the method implemented in the C function poly2()?
- The transformation of poly1() into poly2() was done by hand. Are there any improvements present poly1-O3.S that are also present in poly2-O3.S?