Key Analytics of Algorithm

Points to consider when analysing an Algorithm:

1. A sequence of statements which is executed only once is O(1). It does not depends on how many statements are in the sequence.
2. If a problem of size n can be solved with a simple loop
         for(i=0;i < n;i++)
            {statements;}
   where statements is an O(1) sequence of statements then the time complexity is n*O(1) or O(n)
3. If we have 2 nested loops,
       for(j=0;j < n;j++)
           for(i=0;i < n;i++)
                {statements;}
   then we have n repetitions of an O(n) sequence .so the complexity is n*O(n) which is O(n²)
4. suppose if the inner loop depends on the outer loop index,
       for(j=0;j < n;j++)
           for(i=0;i < j;i++)
                {statements;}
   The inner loop gets executed j times. so the total is n*(n+1)/2 times.so the complexity is O(n²). The result is same as the result for 2 nested loops.so the variable number of iterations of the inner loop doesnt affect.
5. In a loop if a index jumps by an increasing amount in each iteration, such as
       n=1;
       while(n < =x)
       {
           statements;
           n=2*n;
       }
   in which n takes values 1,2,4,8..until it exceeds n.ie n=2⁰,2¹,2²,2³.......This sequence has 1+Log₂n values.so the complexity is O(log₂n)
6. If the number of iterations of the loops decreases by a constant factor with every iteration
       h=n;
       while(h > 0)
       {
           for(i=0;i < n;i++)
               statements;
           h=h/2;
       }
   then there are log₂n iterations of the outer loop and n iterations of the inner loop. so the overall complexity is O(nlogn)