Reference no: EM132637555

Asymptotic working times of the functions given below are indicated next to them. Find another function that calculates the same value for each function more efficiently as stated below.

a) The following function runs in O (n) time:

int g1(int n, int a[]) {
s = 0 ;
for (int i = 1; i < n; ++i)
s = s + a[i] - a[i-1] ;
return s;
}

Find a function that does the same calculation and runs in O (1) time.

b) The following function runs in O (n^2) time:

int g2(int n, int a[]) {
s = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
s = s + a[i]*a[j];
}
}
return s;
}

Find a function that does the same calculation and runs in O (n) time.