Exercise for finding time complexity of an 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)

 Problems

1. order the following functions by growth rate: n, root n, n1.5, n2, n log n, n log log n, n log2 n, n log(n2), 2/n, 2 , 2n/2, 37, n2 log n, n3. Indicate which functions grow at the same rate.
2. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time (GATE CS 2003)
   a) (n log n)
   b) (n)
   c) (log n)
   d) (1)
3.  Programs A and B are analyzed and found to have worst-case running times no greater than 150n log2 n and n², respectively. Answer the following questions if possible:
   a. Which program has the better guarantee on the running time, for large values of n (n > 10,000)?
   b. Which program has the better guarantee on the running time, for small values of n (n < 100)?
   c. Which program will run faster on average for n = 1,000?
   d. Is it possible that program B will run faster than program A on all possible inputs ?