Complexity Analysis & Asymptotic Notations

[ Home Page ]  [ Back ]  [ Content of Contributions ]  [ Movement: Green Leaf World ]

Complexity

The issues to determine how good an algorithm is, can be measured in terms of complexity. It can be classified as,

1. Computational Complexity
2. Time Complexity
3. Space Complexity

The easiest way measure the complexity of an algorithm in terms of Growth of a function. 

GROWTH OF A FUNCTION CAN BE DEFINED BY THE HIGHEST DEGREE OF A POLYNOMIAL EXPRESSION, CALLED ORDER OF NOTATION.

The order of the function f(x)= x² - 3x + 12 is x²

ASYMPTOTIC NOTATION

(Big-Oh, Big-Omega, Big-Theta, Little-Oh and Little Omega)

Most often we calculates time complexity, but in the similar way we can compute space complexity also. Computational complexity is useful when time and space complexity are same for two different algorithm.

You must be aware about the fact of Best Case &  Worst Case of an algorithm before calculating complexity of an algorithm.

Best Case of an algorithm is the situation when the algorithm will compute the result as earliest as possible for sufficient large input value.

Worst Case of an algorithm is the situation when the algorithm will compute the result as longest as possible for sufficient large input value.

Try Your Own

 Calculate the best & worst case for the following problems:

1. Linear Search in an array or linked list.
2. Binary Search in an ordered array.
3. Searching for the maximum or minimum value in an array or linked list.
4. Find highest digit in a number with K digits(K>0).
5. Find a given number is prime or not.
6. Insert in an ordered array.
7. Insert in an ordered linked list.
8. Delete an element from an ordered array.
9. Delete an element from an ordered linked list.