Click here to hide categories Click here to show left categories

User: Home          welcome : Guest          Log In / Register here     




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.

Share this article   |    Print    |    Article read by 10598 times
Author:
Ritika Sood
Lecturer in computer science....Love to do programming...Other interests are sports, freaking out with frnds, travel at beautiful places, watch movies, listen songs....
Related Articles: No related article
Related Interview Questions: No related interview question