Computing Complexity

To compute the complexity, the three basic steps that need to be followed are Select the computational resource (time factor).Find the size of the input, i.e., the variables which make an algorithm to work more. Observer the elementary steps (statements) which are executed for the input size. A piece of code may be of five types Loops, Nested Loops, If-then-else statements, Consecutive statement and Logarithmic complexity. In a loop, a set of statements is executed a number of times. Thus, the run time of a loop is equal to the run time of the statements inside the loop multiplied by the number of iterations. If the loop runs N times, then the time required will be Time multiply by number of loops. Thus, the time complexity of the loop will be : O-N. In if-then-else statements, the part of the code which is to be executed is decided on the basis of the condition test. Thus, the time complexity of the if-then-else statement is the time taken by the condition test plus the time taken by either the then part or the else part. The time complexity of consecutive statements is simply the addition of the complexity of each statement in the sequence. Algorithms that break down the input into two or more sets and proceed with the required set like binary search have logarithmic complexity. The run time of algorithms varies not only for the inputs of different sizes but also for the different inputs of the same size.

To Access the full content, Please Purchase