Reply
Sun 4 Oct, 2020 08:58 am

Complexity

2) Consider the following code.

void f(m){ // where m is a 2d matrix with fixed rows and columns for d in 0..m.rows(){

if m[d][d]==0{

int i=row_index_with_highest_value_in_column(m,d,d+1); if m*[d]!=0{*

swap_rows(m,d,i);

} else {continue;}

}

f=m[d][d];

for i in 0..m[d].cols(){ m[d]*/=f;} for i in d+1..m.rows(){*

f=-m*[d];*

for k in d..m*.cols(){ m**[k]+=m[d][k]*f; }*

}

}

}

Please estimate the time complexity T(r,c)=… for this procedure. Please give the order of

complexity (O) of T(r,c)

• r is the number of rows

• c is the number of columns

• You may assume that the procedure “swap_rows” has time 3

• You may assume that the procedure “row_index_with_highest_value_in_column” being the maximum

of a list has linear time cost (n) in the number of elements it must search through.

Algorithms

3) Given a set of 2d data points it is always possible to plot a polynomial function through them

all. For instance [(1,5),(7,10),(-5,1),(-6,-6)] can be fitted by

Y=6.74 - 1.6097x-0.198x²+0.071x³

Can you find an algorithm to find these equations in general for any set of points? Discuss the

time

complexity.