Assignment 13 - Calculating the order

1. Getting Started.

   Please refer to this page for information on how to work on your assignment.

2. Outline

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

   1. The function f and c × f have the same order for every constant c > 0.
   2. 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.
   3. The following functions all have the same order:
      • n² ;
      • 30 + n² ;
      • 500 × n² + 30 × n + log(n) ;
      • (n - 10) × (n - 20) / 256 ;
      • n² - 123456789 × n ;
      • 0.000001 × n² + 7000000 .
   4. 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) ; (also noted 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² ;
      • n³× log(n) ;
      • 2ⁿ
      • 3ⁿ
      • n!
      • nⁿ
3. Mathematical notation

   In order to work around some severe limitations of early computers, the mathematical notation used in computer science is a simplified but more verbose one compared to pure maths. For instance, the function n^0.7 × log²(n) causes problems because the powers are written in superscript and the × character was not available in the early character sets. Typically, we'll use the following conventions:

   • a×b or a.b noted as: a*b
   • xⁿ noted as: x^n or x*x*…*x (n times)
   • xⁿ⁺¹ as x^(n+1)
   • 2.n².log⁵(n) + 3.n³.log(n) noted as: 2*n^2*log^5(n)+3*n^3*log(n)
4. 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 terms of the form 0*n^a*log^b(n), the output should just be 0*n^0*log^0(n) which will be displayed by the system as 0.

5. 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 and 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 and 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 ordercalc() function should 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 ordercalc() function 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, that variable 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 JavaScript code.