Algorithm Complexity

Here we are talking about computational complexity. Computational complexity is a characterization of the time or space requirements for solving a problem by a particular algorithm. These requirements are expressed in terms of a single parameter that represents the size of the problem.

Given a particular problem, say one of the simplification problems. Let ‘n’ denote its size. The time required of a specific algorithm for solving this problem is expressed by a function.

f : R  R

such that f(n) is the largest amount of time needed by the algorithm to solve the problem of size n. Function ‘f’ is usually called the time complexity function.

Thus, we conclude that the analysis of the program requires two main considerations:

• Time Complexity

• Space Complexity

Time Complexity

The time complexity of a program/algorithm is the amount of computer time that needs to run to completion.

While measuring the time complexity of an algorithm, we concentrate on developing only the frequency count for all key statements. This is because, it is often difficult to get reliable timing figure because of clock limitations and the multiprogramming or the sharing environment.

Space Complexity

The space complexity of a program/algorithm is the amount of memory that it needs to run to completion.

The space needed by the program is the sum of the following components:

Fixed space requirement: This includes the instruction space, for simple variables, fixed size structured variables, and constants.

Variable space requirement: This consists of space needed by structured variables whose size depends on particular instance of variables. It also includes the additional space required when the function uses recursion.