Problem 1. (1)Sort the following functions of n in the increasing order from left to right:

n, n^2, n log n, log^10 n, n^10, 2^n, n^3

(2) Specify the calculation cost for each loop below:

   1.

      for( i=0; i<n; i++) sum++;

   2.

      for( i=0; i<n; i++)
        for( j=0; j<n; j++) sum++;

   3.

      for( i=0; i<n; i++)
        for( j=0; j< n*n;j++) sum++;

   4.

      for( i=0; i<n; i++)
        for( j=0; j<i; j++) sum++;

Problem 2

Fill in the table with the execution times for the 4 loops in Problem 1 (2). Use some time function for the actual time measurement.

  1.
  +----+---------+---------+---------+---------+---------+
  |  n |  2000000|  4000000|  6000000|  8000000| 10000000|
  +----+---------+---------+---------+---------+---------+
  |time|         |         |         |         |         |
  +----+---------+---------+---------+---------+---------+

  2.
  +----+---------+---------+---------+---------+---------+
  |  n |     2000|     4000|     6000|     8000|    10000|
  +----+---------+---------+---------+---------+---------+
  |time|         |         |         |         |         |
  +----+---------+---------+---------+---------+---------+

  3.
  +----+---------+---------+---------+---------+---------+
  |  n |      100|      200|      300|      400|      500|
  +----+---------+---------+---------+---------+---------+
  |time|         |         |         |         |         |
  +----+---------+---------+---------+---------+---------+

  4.
  +----+---------+---------+---------+---------+---------+
  |  n |     2000|     4000|     6000|     8000|    10000|
  +----+---------+---------+---------+---------+---------+
  |time|         |         |         |         |         |
  +----+---------+---------+---------+---------+---------+

Don't submit the program, but the results and a brief explanation.

Problem 3:
This task is to implement two different programs suggested below that determine the kth largest number from a group of n numbers and compare their performances. For performance purpose use value of k=n/2 and vary n from 5000 to 200000 with an increment of 10000. Draw a table showing the running time of your program for each value of n.
 
Solution a: One way to solve this problem would be to read the n numbers into an array, sort the array in decreasing order by some simple algorithm such as bubblesort, and then return the element in position k.

Solution b: A somewhat better algorithm might be to read the first k elements into an array and sort them (in decreasing order). Next, each remaining element is read one by one. As a new element arrives, it is ignored if it is smaller than the kth element in the array. Otherwise, it is placed in its correct spot in the array, bumping one element out of the array. When the algorithm ends, the element in the kth position is returned as the answer (Can you think of a better way to implement the last step using the 'Queue' data structure).



4. Write a C program to sort a list of numbers using Selection sort. 
5. Write a C program to sort a list of numbers using Merge sort. 

File: hw1_asymptotic_notation.pdf