I'm having issues understanding Asymptotic Analysis or Complexity, I tried the following link and read the complete article, this however didn't give me final answer to my question, which is:
Am I supposed to write complexity for each line of code and sum them up or something else? My teacher didn't quite explained how to do it but wants it done.
Condition: a knight (chess) must cross an iced-lake (m x n matrix) and get his buddy from the other side of the lake with given obstacles. Every time he jumps, the cell of the matrix that he jumps on becomes an obstacle (ice falls). After he gets his buddy he must return to the starting point following a different route. Starting point is bottom corner left cell, his buddy is located on top right corner cell
I used Backtracking for this algorithm and the problem that remains is calculating time or asymptotic complexity. Code below:
#include<stdio.h>
#include<conio.h>
#define N 50
typedef struct{
int x;
int y;
} coordonate;
int sol=0,m,n;
coordonate vectSol[N];
void jump(int xL,int yL,int xD,int yD,int obstacole[N][N],int steps,coordonate road[N]);
int main(){
int i,j,x,y,obstacole[N][N],nrObs;
int KnightMatrixRoad[N][N], KnightMatrixBack[N][N];
coordonate pathKnight[N],pathBack[N];
printf("m=");
scanf("%d",&m);
printf("n=");
scanf("%d",&n);
printf("Nr. of obstacles: ");
scanf("%d",&nrObs);
for(i=0;i<nrObs;i++){
printf("Insert obstacle %d through space bar (x,y):",i+1);
scanf("%d %d",&x,&y);
obstacole[y-1][x-1]=1;
}
jump(0,0,m-1,n-1,obstacole,0,pathKnight);
for(i=0;i<=sol;i++){
obstacole[vectSol[i].y][vectSol[i].x]=1;
pathKnight[i]=vectSol[i];
vectSol[i].x=0;
vectSol[i].y=0;
}
sol=obstacole[n-1][m-1]=obstacole[0][0]=0;
jump(m-1,n-1,0,0,obstacole,0,pathBack);
for(i=0;i<=sol;i++){
pathBack[i]=vectSol[i];
vectSol[i].x=0;
vectSol[i].y=0;
}
for(i=0;(pathKnight[i-1].x!=m-1) || (pathKnight[i-1].y!=n-1);i++){
KnightMatrixRoad[pathKnight[i].y][pathKnight[i].x]=i;
}
puts("\nPath to his buddy:\n");
for(i=n-1,sol=0;i>=0;i--){
for(j=0;j<m;j++)
printf("%3d",KnightMatrixRoad[i][j]);
printf("\n\n");
}
for(i=0;((pathBack[i-1].x!=0) || (pathBack[i-1].y!=0)) || i==0;i++){
KnightMatrixBack[pathBack[i].y][pathBack[i].x]=i;
}
puts("\nPath back to starting point:\n");
for(i=n-1,sol=0;i>=0;i--){
for(j=0;j<m;j++)
printf("%3d",KnightMatrixBack[i][j]);
printf("\n\n");
}
getch();
}
void jump(int xLocal,int yLocal,int xDest,int yDest,int obstacole[N][N],int steps,coordonate road[N]){
int i,j;
int tempObstacole[N][N];
for(i=0;i<n;i++)
for(j=0;j<m;j++){
tempObstacole[i][j]=obstacole[i][j];
}
road[steps].x=xLocal;
road[steps].y=yLocal;
if(xLocal==xDest && yLocal==yDest){
if(sol==0 || steps<sol){
for(i=0;i<=sol;i++){
vectSol[i].x=0;
vectSol[i].y=0;
}
sol=steps;
for(i=0;i<=sol;i++)
vectSol[i]=road[i];
}
}
if(sol==0 || steps+1<sol){
tempObstacole[yLocal][xLocal]=1;
if(yLocal+2<n && xLocal+1<m && !(tempObstacole[yLocal+2][xLocal+1]))
jump(xLocal+1,yLocal+2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal+2<n && xLocal-1>=0 && !(tempObstacole[yLocal+2][xLocal-1]))
jump(xLocal-1,yLocal+2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-2>=0 && xLocal+1<m && !(tempObstacole[yLocal-2][xLocal+1]))
jump(xLocal+1,yLocal-2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-2>=0 && xLocal-1>=0 && !(tempObstacole[yLocal-2][xLocal-1]))
jump(xLocal-1,yLocal-2,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal+1<n && xLocal+2<m && !(tempObstacole[yLocal+1][xLocal+2]))
jump(xLocal+2,yLocal+1,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal+1<n && xLocal-2>=0 && !(tempObstacole[yLocal+1][xLocal-2]))
jump(xLocal-2,yLocal+1,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-1>=0 && xLocal+2<m && !(tempObstacole[yLocal-1][xLocal+2]))
jump(xLocal+2,yLocal-1,xDest,yDest,tempObstacole,steps+1,road);
if(yLocal-1>=0 && xLocal-2>=0 && !(tempObstacole[yLocal-1][xLocal-2]))
jump(xLocal-2,yLocal-1,xDest,yDest,tempObstacole,steps+1,road);
}
}
When you're analyzing code, you have to analyse it line by line, counting every operation/recognizing time complexity, in the end, you have to sum it to get whole picture.
For example, you can have one simple loop with linear complexity, but later in that same program you can have a triple loop that has cubic complexity, so your program will have cubic complexity. Function order of growth comes into play right here.
Let's look at what are possibilities for time complexity of an algorithm, you can see order of growth I mentioned above:
Constant time has an order of growth 1, for example: a = b + c.
Logarithmic time has an order of growth LogN, it usually occurs
when you're dividing something in half (binary search, trees, even loops), or multiplying something in same way.
Linear, order of growth is N, for example
int p = 0;
for (int i = 1; i < N; i++)
p = p + 2;
Linearithmic, order of growth is n*logN, usually occurs in divide and conquer algorithms.
Cubic, order of growth N^3, classic example is a triple loop where you check all triplets:
int x = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
x = x + 2
Exponential, order of growth 2^N, usually occurs when you do exhasutive search, for example check subsets of some set.
I think that your teacher wanted to get whole picture where you'll figure out that backtracking algorithms are very very slow.