4. Time and Space complexity

1. Time complexity

: basically depends on the procedure that you are adopting.

n : some number of elements 

O(n), bigO to measure time consuming to take a task.

For finding the time complexity either you can measure the time based on the work that you are doing, means according to your procedure, if you're clear with your procedure, you can know the time, or else from the code, program code also you can find the time complexity. 

 

when something is successively divided until it reaches one, that is represented as log,

for(i = n;i>1;i=i/2)

{

}

matrixs (n x n) to search all elements O(n^2)

                    to search row O(n)

 

array of linked list 

O(m + n ) => O(n)

 

if you're spending time upon a tree, along the height of a tree, then it is O(log n)

 

2. Space complexity 

: how much space is consumed in main memory during the execution of a program.

we're not concerned about the number of bytes. 

 

example 

 

void swap(x, y)

{

int t;

t = x;     ---1

x = y;     ---1

y = t;     ---1

}

f(n) = 3 = O(1)

 

int sum(int a[], int n)

{

 int s, i;

 s=0; -------1 

 for(i=0; i<n ; i++)       --- n+1 , sum = 2(n+1)

{

 s = s+A[i];   --- n 

}

return s;  -------1

}

f(n) = 2n+3, O(n)

 

void Add(int n)

{

int i, j;

for(i=0 , i<n ; i++) ---------- n+1

{

  for(j=0; j<n; j++)  ---------- n * n+1 (nested loop)

  {

      c[i][j] = A[i][j] + B[i][j] -------n * n

  }

}

}

f(n) = 2*n^2 + 2n + 1 , O(n^2)