Time complexity

Time complexity is the computational complexity that measures the  time taken for running an algorithm.

The big O notation is used to express time complexity which is typically  is commonly expressed

where n is the input size measured by the number of bits needed for representing it.


Time complexity is estimated by counting the number of elementary operations performed by the algorithm. The amount of time taken and the number of elementary operations performed by the algorithm differ by atmost a constant factor.

• Constant time Complexity :  O(1)  The number of operations for the algorithm doesn't actually change as the problem size increases. it is mostly a program that contains no loops or recursive calls. it can also be a for loop that runs a constant number of times.

         For example:

         a for loop with a constant range:

        >>> for i in range(0,c):

       print i

        This loop will run in constant time for  c = constant integer

• Linear Complexity: O(n) .The algorithm is linear, doubling the problem size also doubles the number of operations required. Algorithms that deal with lists or similar kinds in which each element has to be accessed are linear because they touch each element of the sequence a constant (>0) number of times.

• Quadratic Complexity O(n^2) :Doubling the problem size multiplies the operation count by four. Time complexity of 2 nested loops will give Quadratic Complexity.
 For example:
  >>> for i in range(0,c):      
               for  j in range(0,c):
                        print i, j         

          Selection sort and Insertion Sort have O(n^2) time complexity

• Logarithmic Complexity :   O (log(n)) Such functions have a complexity that grows as the log of at least one of the inputs. In the loop the constant factor is multiplied or divided by another constant factor. Binary search , is logarithmic in the length of the list being searched. The base used to take the logarithm makes no difference, since it just  multiplies the operation count by a constant factor. 

            >>> for i in range(0,c, /c):

       print i

• Log linear Complexity:O(nlog(n)) Merge sort algorithm has log-linear time complexity