Lovedeep Singh - timecomplexity

<<< Data Structures and Algorithms

Time Complexity

Time Complexity provides an efficient and easy notation to compare the performance of two algorithms without giving any undue advantage to a particular algorithm becuase of the factors such as the execution machine, human errors etc.

Time Complexity T , of an algorithm A is an approximate estimate of the time taken by the function, infact in a more strict sense it actually represents the nature of growth of time of the algorithm with the increasing size of input

For comparisons, we are concerned with the behaviour of an algorithm at very large input sizes

This is time complexity graph for most of the common problem scenarios and algorithms in Computer Science

We can summarize this as follows:

O(1) - time taken independent of input size
O(log(n)) - input generally reduces in size by some factor at each step until algorithm terminates
O(sqrt(n)) - this is an algorithm that is better than O(n) but more consuming than O(log(n)). This is usually in scenarios where input is divided in sqrt(n) parts which are of size sqrt(n) each
O(n) - algorithm needs to iterate over the input some fixed number of times
O(n log(n)) - algorithms generally involves sorting as an intermediate and most costly step or uses some other sub algorithm that had log(n) time complexity n number of times
O(n^2) - algorithms goes through all pair of elements
O(n^3) - algorithms goes through all triplets of elements
O(n^k) - algorithms goes through all k groupings of elements
O(2^n) - algorithms goes through all subsets of elements
O(n!) - algorithms goes through all permutation of elements

Page updated

Google Sites

Report abuse