Time complexity-TC concepts

Time complexity-TC concepts

1. always consider worst case

2. Asymptotic notations

   • Big O
     • rules to calculate
       • ignore constant multiplier
       • ignore lower powers
     • indicate upper bound-worst case
     • T(n) <=c f(n), n>N, T(n) -- O(f(n))
     • TC function is less than or = to upper bound
     • mostly used
   • Big omega
     • indicate lower bound
     • TC function is greater than or = to lower bound
     • T(n)>= c f(n),n>N, T(n) -- omega f(n)
   • Big theta
     • bounded above and below
     • c1. g(n) <= T(n) <=c2 .f(n), n>N, T(n)-- theta f(n)

3. basic rules

   • rule of sums
     • when 2 for loop one after another
   • rule of product
     • when 2 nested for loops

4. time v/s space complexity trade off

5. O(1)

   • running time independent of input size

6. order of efficiency

   • O(1) > O(log n) > O(n) > O(n log n) > O(n ^2 ) > O(n ^3 )>O(2^n)

7. method of induction for solving problems

8. Masters theorm