Time and Space complexity

Time and Space complexity is a very important part of Data Structure. Less time and space complexity makes our program more efficient. While writing any program you must consider time and space complexity as the primary requirement. If you write a program having more time and space complexity it makes your program bulky. It is important to minimize the time and space complexity as much as it is possible.

Time complexity

Time Complexity is defined as the time taken to execute each statement of the algorithm. Time and space complexity can be estimated by the number of elementary operations performed by the algorithm. We use Asymptotic Notation to express the time complexity. Time complexity is most commonly expressed using big O notation.  https://en.wikipedia.org/wiki/Big_O_notation

	Example 1:
     int main () {
	     printf ("Hello, World!");	     // time complexity   O ( 1 )
	}

In Example 1 there is a single statement that takes a unit of time to execute. The Time complexity of this program is big oh (1).

	Example 2:
    int main () {
	int number = 5;             // time complexity    O(1)
	if (number < 0) {                    // time complexity    O(1)
	printf ("You entered %d.\n", number);
	}
	printf ("The if statement is easy.");
	}

In example 2 each statement takes a unit of time to execute. The time taken by the if, if else and else statement is 0(1). Hence the overall Time complexity of the whole program is 0(1).

	Example 3:
    int main(){

	int length=11;
	int  i ;
	for (i = 1; i <= length ; ++i)           //time complexity      O(n)
	{
	    printf ("%d ", i);
	}
	return 0;
	}

In Example 3 output is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11. For loop, the statement is run 11 times the for printing required output. If the Length is N then For statement run N times for printing required output. Hence the Time complexity of For loop in 0(n);

Example 4:
int main()
{
int i, j;
int matrix[ROW][COL] = { { 1, 2, 3 },
                         { 4, 5, 6 },
                         { 7, 8, 9 } };
    printf ("Given matrix is \n");
    for (i = 0; i < ROW; i++) {             // time complexity     0(n)
          for (j = 0; j < COL; j++) {              // time complexity    0(n)
                 printf ("%d ", matrix[i][j]);
              }printf ("\n");
       }
return 0;
}

In Example 4 there are two loops that are used to print 2D Array as we know one For loop takes 0(n) time. In the case of nested loop 0(n*n) = 0(n^2) for two nested loops. Similarly, a single while loop takes 0(n) time.

Example 5: 
int binarySearch (int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (array[mid] == x)
      return mid;
    if (array[mid] < x)
      low = mid + 1;
     else
      high = mid - 1;
  }
     return -1;
}

In Example 5 as we know while loop takes 0(n) time and every time the size becomes half. The make-time complexity reduces and becomes 0(log n).

AlgorithmTime Complexity
linear SearchO (n)
Binary SearchO (log n)
Bubble SortO ( n^2)
Selection SortO ( n^2)
Insertion SortO ( n^2)
Merge SortO (n log n)
Quick SortO (n log n)

Space complexity

Space complexity is defined as the number amount of memory used by your program. As an application user, I want that what application I use takes less time as well as less space. Hence it is important to use the minimum possible space for reducing the space complexity. For Example, when we create a stack and queue we required additional space, and in programs where we use hashing required extra space.

	Example 1:
    int add 
	int addNumbers(int n) {
	if (n != 0)
	return n + addNumbers(n - 1);
	else
	return n;
	}

Here each function call adds extra space to the stack and makes their space complexity 0(n).

Note: It is necessary to mention that Space complexity depends upon a variety of things such as programming language, compiler, or even the machine running the program.

Ritesh Pandey
Ritesh Pandey

Leave a Reply

Your email address will not be published. Required fields are marked *