Please refer to this page for information on how to work on your assignment.
The order of a function is a rough measure for its growth rate. There are some major principals:
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^{2}(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:
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.
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.