Time Complexity

Time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.

Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.


Execution Time Cases

There are three cases which are usually used to compare various data structure's execution time in a relative manner.


Worst Case

This is the scenario where a particular data structure operation takes maximum time it can take.

If an operation's worst case time is ƒ(n) then this operation will not take more than ƒ(n) time where ƒ(n) represents function of n.


Average Case

This is the scenario depicting the average execution time of an operation of a data structure.

If an operation takes ƒ(n) time in execution, then m operations will take mƒ(n) time.


Best Case

This is the scenario depicting the least possible execution time of an operation of a data structure.

If an operation takes ƒ(n) time in execution, then the actual operation may take time as the random number which would be maximum as ƒ(n).


Introduction to Algorithms Previous Next DS Arrays