Worksheet W.A.21.1                        Name ______________________________

ORDER OF ALGORITHMS

Determine the order of the following algorithms:

Question 1:

int  answer  (int  n)

{

if (1 == n)  return 2;

else  return  2 * answer (n - 1);

} 

a.   O(1)     b. O(log n)     c. O(n)     d. O(n2)     e. O(2n)           Answer = ________

 Briefly justify your answer:

   Question 2:

 Assume the following definitions apply in question 2:

 const int N = 100;

apmatrix<int> data(N,N);

void  invert (apmatrix<int>  data)

{

        for (int  row=0; row < N; row++)

                for (int  col=0; col<N; col++)

                        data [row][col] = (0 == data [row][col]);

}

a.  O(1)     b. O(log n)     c. O(n)     d. O(n2)     e. O(2n)           Answer = ________

Briefly justify your answer:

 const int N = 100;

apvector<int>  list(N);

void reverse (apvector<int> &numbers)

{

        int  temp;

         for (int  loop=0; loop<=(N-1)/2; loop++)

        {

                temp = numbers [loop];

                numbers [loop] = numbers [N-loop-1];

                numbers [N-loop-1] = temp;

        }

}

 a.   O(1)     b. O(log n)     c. O(n)     d. O(n2)     e. O(2n)           Answer = ________

Briefly justify your answer to the right of the algorithm.

Question 4:

/*  This program finds the most frequently occurring value in a list of numbers stored in a text file, shortnum.txt.  If there are multiple answers, the algorithm will find only one of them.  The integers in the file range from 1..M, and there are N values in the file. */

const  int  M = 100;

main ()

{

        ifstream  inFile;

        int  largestCount = INT_MIN, count, number, mode;

        for (int  loop=1; loop<=M; loop++)

        {

inFile.open ("shortnum.txt", ios::in);

count = 0;

while (inFile >> number)

        if (loop == number)

                count++;

if (count > largestCount)

{

        largestCount = count;

        mode = loop;

}

inFile.close();

        }

        cout << "mode = " << mode << endl;

}

How many times will the statement, if (loop == number) be executed?

a.  N     b. M     c. N2     d. M2     e. N x M                        Answer = ________

Briefly justify your answer to the right of the algorithm.