Basic Concepts - Types of algorithm complexities

There are two types of algorithm complexity:

1. Space Complexity

2. Time Complexity

1. Space Complexity: It is the amount of memory which is needed by the algorithm (program) to run to completion. We can measure the space by finding out that how much memory will be consumed by the instructions and by the variables used.

E.g.

Suppose we want to add two integer numbers. To solve this problem we have following two algorithms:

Algorithm 1:                            Algorithm 2:

Step 1- Input A.                      Step 1- Input A.

Step 2- Input B.                      Step 2- Input B.

Step 3- Set C: = A+ B.             Step 3- Write: ‘Sum is ‘, A+B.

Step 4- Write: ‘Sum is ‘, C.        Step 4- Exit.

Step 5- Exit.

Both algorithms will produce the same result. But first takes 6 bytes and second takes 4 bytes (2 bytes for each integer). And first has more instructions than the second one. So we will choose the second one as it takes less space than the first one.

2. Time Complexity: It is the amount of time which is needed by the algorithm (program) to run to completion. We can measure the time by finding out the compilation time and run time. The compilation time is the time which is taken by the compiler to compile the program. This time is not under the control of programmer. It depends on the compiler and differs from compiler to compiler. One compiler can take less time than other compiler to compile the same program. So we ignore the compilation time and only consider the run time. The run time is the time which is taken to execute the program. We can measure the run time on the basis of number of instructions in the algorithm.

E.g.

Suppose we want to add two integer numbers. To solve this problem we have following two algorithms:

Algorithm 1:                                       Algorithm 2:

Step 1- Input A.                                 Step 1- Input A.

Step 2- Input B.                                 Step 2- Input B.

Step 3- Set C: = A+ B.                        Step 3- Write: ‘Sum is ‘, A+B.

Step 4- Write: ‘Sum is ‘, C.                   Step 4- Exit.

Step 5- Exit.

Suppose 1 second is required to execute one instruction. So the first algorithm will take 4 seconds and the second algorithm will take 3 seconds for execution. So we will choose the second one as it will take less time.

Click here to go on website