CS 154 HW7 problem 3

Consider C functions poly1() and poly2() (also below) and its assembly with no optimization poly1-O0.S and with optimization poly1-O3.S.
```/*
** 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;
}
```
1. What is the asymptotic efficiency O(n) for the method implemented in the C function poly1()?
2. 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?
3. 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()?
4. 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?