## Complexity

• The complexity of an algorithm M is the function f(n) which gives the running time and/or
storage space requirement of the algorithm in terms of the size ‘n’ of the input data.
• Mostly, the storage space required by an algorithm is simply a multiple of the data size ‘n’.
• Complexity mainly refer to the running time (Time Complexity) of the algorithm.
• The function f(n), gives the running time of an algorithm, depends not only on the size ‘n’ of
the input data but also on the particular data.

#### Type of Complexity

##### (A) Space Complexity
• The space complexity of a program is the amount of memory it needs to run to completion.
• The space need by a program has the following components: –
• Instruction space: Instruction space is the space needed to store the compiled version of the program instructions. The amount of instructions space that is needed depends on some factors as :-
• The compiler used to complete the program into machine code.
• The compiler options in effect at the time of compilation.
• The target computer.
• Data space: Data space is the space needed to store all constant and variable values. Data space has two components-
(i) Space needed by constants and simple variables in program.
(ii) Space needed by dynamically allocated objects such as arrays and class instances.
• Environment stack space: The environment stack is used to save information needed to resume execution of partially completed functions.

##### (B)Time Complexity
• The time needed by an algorithm expressed as a function of the size of a problem is called the time complexity of the algorithm.
• The time complexity of a program is the amount of computer time it needs to run to completion.
• The limiting behavior of the complexity as size increases is called the asymptotic time complexity. It is the asymptotic complexity of an algorithm, which ultimately determines the size of problems that can be solved by the algorithm.

## Notation for complexity

The complexity may exists in three forms –

(A) Best Case (B) Average Case (C) Worst Case

#### (A) Best Case

• The minimum possible value of f(n) is called the best case.

#### (B) Average Case

• The expected value of f(n).

#### (C) Worst Case

• The maximum value of f(n) for any key possible input.

298 total views,  1 views today

Categories: Algorithm & Design