Every algorithms requires some amount of computer time to execute its instruction to perform the task. This computer time required is called time complexity.

Definition :

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its execution.

• The total time taken by the algorithm or program is calculated using the sum of the time taken by each of executable statement in algorithm or program.
• Time required by each statement depends on :

1.  Time required for executing it once.
2.   Number of times the statement is executed.

There are difference types of time complexities which can be analyzed for an algorithm :

1. Best Case :

• It is a measure of the minimum time that the algorithm will require for an input of size ‘n’.
• The running time of many algorithms varies not only for the inputs of different sizes but also for the different inputs of same size.
• For example in the running time of some sorting algorithms, the sorting will depend on the ordering of the input data.
• Therefore, if an input data of ‘n ’ items is presented in sorted order, the operations performed by the algorithm will take the last time.

 

1. Worst Case :

• It is a measure of the maximum time that the algorithm will require for an input of size ‘n’.
• Therefore, if various algorithms for sorting are taken into account and say ‘n’ input data items are supplied in reverse order for any sorting algorithms, then the algorithm will require n² operations to perform the sort which will correspond to the worst case time complexity of the algorithm.

1. Average Case :

• The time that an algorithm will require to execute a typical input data of size ‘n’ is known as average case time complexity .
• We can say that the value that is obtained by averaging the running time of an algorithm for all possible inputs  of size ‘n’ can determine average case time complexity.
• The computation of exact time taken by the algorithm for its execution is very difficult.
• Thus, the work done by an algorithm for the execution of the input of size ‘n’ define the time analysis as function f(n) of the input data items.

•  Example :

                    Int sum(int a, int b){
                    Return a+b;
                    }

• In above sample code, it requires 1 unit of time to calculate a+b and 1 unit of time to return the value.
• That means, totally it takes 2 units of time to complete its execution, And it does not change based on the input values of a and b.
• That means for all input values, it requires same amount of time i.e. 2 units.
• If any program requires fixed amount of time for all input values then its time complexity is said to be Constant Time Complexity.