Growth of Functions

Growth of Functions

Algorithm’s rate of growth enables us to figure out an algorithm’s efficiency along with the ability to compare the performance of other algorithms. Input size matters as constants and lower order terms are influenced by the large sized of inputs.

For small inputs or large enough inputs for the order of growth of execution time, we can find out the more efficient algorithm among all other algorithms with the help of asymptotic notation.

However, for large inputs where the size of inputs grows without bound become the main concern for the increase in running time of an algorithm. Asymptotic analysis of an algorithm can be simplified with Asymptotic notations.

Asymptotic Notations

Asymptotic notations are used to represent the asymptotic( within limit) running time of an algorithm. These are defined using functions. These can be implied on functions that provide aspects like running time of algorithms and amount of space that they use and more.

Theta Notation ( Θ Notation) :

It bounds a function inbetween the constant factors that are tightly bound. In this, lower order terms of an asymptotically positive function are ignored as they are insignificant and coefficient of order term is also ignored. It asymptotically bounds a function from above and below.

Θ (g(n)) = {  f(x) : there exist positive constants a1,a2 and n0 such that  0 <= a1g(n)<= f(n) <= a2g(n) for all n>= n0 }

Big O Notation ( O Notation) :

It asymptotically bounds a function only from above. It is used to get upper bound on a function,  to within a constant factor. we use it to bound the worst case runntime of an algorithm

O (g(n)) = {  f(x) : there exist positive constants a and n0 such that  0 <= f(n) <= ag(n) for all n>= n0 }

Big Omega Notation ( Ω Notation) :

It asymptotically bounds a function only from below. It is used to get lower bound on a function. we use it to bound the best case running time of an algorithm.

Ω (g(n)) = {  f(x) : there exist positive constants a and n0 such that  0 <= ag(n) <= f(n)  for all n>= n0 }