Complexity of Algorithm

It is very convenient to classify algorithm based on the relative amount of time or relative amount of space they required and specify the growth of time/space requirement as a function of input size.

1. Time Complexity: Running time of a program as a function of the size of the input.
2. Space Complexity: Some forms of analysis could be done based on how much space an algorithm needs to complete its task. This space complexity analysis was critical in the early days of computing when storage space on the computer was limited. When considering this algorithm are divided into those that need extra space to do their work and those that work in place.

But now a day's problem of space rarely occurs because space on the computer (internal or external) is enough.

Broadly, we achieve the following types of analysis -

• Worst-case: f (n) defined by the maximum number of steps taken on any instance of size n.
• Best-case: f (n) defined by the minimum number of steps taken on any instance of size n.
• Average case: f (n) defined by the average number of steps taken on any instance of size n.