Topic : Performance Analysis of Algorithms

Performance of an algorithm is a process of making evaluative judgement about algorithms that are used to solve the same problem.

Loading...

Taking too long?

Reload document

| Open in new tab

Download [358.00 B]

Space Complexity: Amount of memory an algorithm needs to run to completion.Space needed by algorithms is a combination of two components:
Fixed Part includes the instruction space (i.e. Code, Simple Variables, Fixed components, Constants etc.
Variable Part includes space needed by component variables whose size is dependent upon particular problem instance.

Time Complexity: Amount of time an algorithm needs to run to completion.
We can have three cases to analyze an algorithm:

Best Case − Minimum time required for program execution.
Average Case − Average time required for program execution.
Worst Case − Maximum time required for program execution

Asymptotic Notation of an algorithm is a mathematical representation of its complexity.

In asymptotic notation, when we want to represent the complexity of an algorithm, we use only the most significant terms in the complexity of that algorithm and ignore least significant terms in the complexity of that algorithm

Big – Oh notation is used to define the Upper bound (Worst Case) of an algorithm in terms of Time Complexity.
That means Big – Oh notation always indicates the maximum time required by an algorithm for all input values. That means Big – Oh notation describes the worst case of an algorithm time complexity.

Big – Omega notation is used to define the lower bound (Best Case) of an algorithm in terms of Time Complexity.
That means Big-Omega notation always indicates the minimum time required by an algorithm for all input values. That means Big-Omega notation describes the best case of an algorithm time complexity.

Big – Theta notation is used to define the average bound (average case)of an algorithm in terms of Time Complexity.
That means Big – Theta notation always indicates the average time required by an algorithm for all input values. That means Big – Theta notation describes the average case of an algorithm time complexity.