Question

What is a growth function? How does it relate to the efficiency of an algorithm? Explain with example.

Answer 1

Growth function :

Growth function is a simple characterization to calculate the efficiency of an algorithm. Andit also allows us to compare the relative performance of alternative algorithms.

It is related to the efficiency of an algorithm as the growth of a function tells us how efficiently a programs runs in terms of time bound.

The efficiency of any algorithm is the running time required of an algorithm to run . And it increases with the size of the input in the limit, as the size of the input increases without bound.

Calculate efficiency of an algorithms are :

Asymptotic notation : These notations are used to describe the asymptotic running time of an algorithm in terms of natural numbers.

Different notations of this are :

1. O-notation : It termed as "big-oh notation", and is used to describe the upper bound of an algorithm.

2.  Ω-notation: It termed as "omega notation", and is used to denotes the lower bound of an algorithm.

3. Θ-notation : It termed as "Theta Notation" , and is used to analyze the average case complexity of an algorithm.

Example :

Efficiency of Linear Search Algorithm in :

1. O-notation : O(n) where n is the is the size of the array

2.  Ω-notation :   Ω(1)

3. Θ-notation : Θ(n) where n is the size of the array.