Time complexity of algorithm is estimated in the following cases:
Best Case:
The
input instance for which the algorithm takes the minimum possible time is
called the best case and the time complexity for such a case is known as the
Best case time complexity.
Worst Case:
The input
instance for which the algorithm takes the maximum possible time is called the
Worst case and the time complexity for such a case is known a s the worst case
time complexity. This is the most commonly used.
Average Case
It is the
average of time taken by various possible input instances. For example, if we
are searching for an element in a list, the average case measures the average
of time taken by the search for the first element, the second element,… the
last element and also an unsuccessful search.
Example for Calculating time
complexity of Linear Search Algorithm:
- Linear search in array of size n (8 in the example below)
Time Complexity can be measured by using any one of the following
techniques.
Note:
- The success of operation count technique depends upon careful selection of the key operations
- The operation count technique doesn’t count the time spent in other parts of the program except the key operations
Step Count: The technique counts the total number of steps
executed by a given program/algorithm.
To compute step count, there is a
technique know as PROFILING.
Profiling: In this method, we tabulate the number of steps per
execution (s/e) of each statement, the number of times a statement is executed
(frequency) and the product of the s/e and frequency. If we sum up the products
for all statements, we will get the step count.
Example for calculating time complexity:
Let us consider an iterative
function to sum up a list of numbers.
<<<<< Previous Home Continue >>>>>>
