CS 154 HW7 problem 3

/*
** 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?