Assignment 13 - Calculating the order

You can download this homework and set the permissions with the commands

      cd ~/public_html
      wget http://www.comp.nus.edu.sg/~gem1501/assignment13.html
      chmod 755 *.html

Outline
The order of a function is a rough measure for its growth-rate. There are some major principals:

The function f and c*f have the same order for every constant c>0.
If there is a constant c such that for all n>c the relation f(n) < c*g(n) holds then the order of f is below the order of g and the functions f+g and g have the same order.
The following functions have all the same order: n*n, 30+n*n, 500*n*n+30*n+log(n), (n-10)*(n-20)/256, n*n-123456789*n, 0.000001*n*n+7000000. One also writes n^2 for n*n and n^3 for n*n*n.
The following functions are listed in ascending order, therefore if f is listed somewhere before g then the order of f+g and g is the same: 1, 256, 3, log(n-50), log(n)*log(n), n^0.005, n^0.7, n^0.7*log(n), n^0.7*log(n)*log(n), n, n*log(n), n^1.414*log(n), n^1.415, n^2, n^3*log(n), 2^n, 3^n, n!, n^n. Note that one often writes log^2(n) for log(n)*log(n), log^3(n) for log(n)*log(n)*log(n) and so on.

The goal
The goal is to compute simple expressions giving the order of a complicated one. If the input is for example 2*n^2*log^5(n)+3*n^3*log(n) then the output should be n^3*log(n). The second term grows faster than the first one, thus the first one can be ignored. Furthermore, in the second term the factor 3 can be set to 1. In the case that the input is the sum of term of the form 0*n^a*log^b(n), the output should just be 0*n^0*log^0(n) what will be displayed by the system as 0.

What has to be done in detail
The global variable "orderresult" is a record consiting of the following three fields: orderresult.factor, orderresult.power, orderresult.logpower. If these fields have the values a,b,c then they represent the function a*n^b*log^c(n). Furthermore, orderlist is a global variable which is an array of four records orderlist[k] for k=0,1,2,3. Assume that orderlist has the following values:

  k     orderlist[k].factor   orderlist[k].power  orderlist[k].logpower
  0                  2                     3                   1
  1                  0                     0                   0
  2                  1                     1                   0
  3                  4                     2                   2

Then it represents the function 2*n^3*log(n)+0+n+4*n^2*log^2(n). The order of this function is n^3*log(n), so the function ordercalc() shoud compute these values and then carry out the following assignments (based on the outcome of these calculations):

  orderresult.factor = 1;
  orderresult.power = 3;
  orderresult.logpower = 1;

Note that the function ordercalc() has to inspect all values fields of the array orderlist. It does this from the beginning to the end. In the case that the order is properly above the current values in orderresult, the variable orderresult has to be updated. This comparison and this update are missing in the function below. Find this place and update the inner loop accordingly, it is as a comment in the Java Script code.

Java Script starts here.

Java Script ends here.