Reference no: EM13162707

1.(20 pts) For each of the following program fragments(expressions), give an analysis of the running time in terms of the big-O notation.

 

 

a. cin >> n;

total = 0;

while (total < n/2)

cout << total;

total++;

 

b. cin >> n

count=0;

do

      count = count + 2;

      for(i=0; i< count; i++)

           cout << "Just a test"

while(count <= n)

 

 

c. cin >> n;

     sum = 0;

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

          for (int j = 10; j < n * n; j++)

              sum++;

 

 

d. cin >> n;

     k = n;

     sum = 0;

     while (k > 1)

     {

          sum++;

          k = k/2;

          test(n);

     }

 

     void test(int x)

     {

     for(int i =0; i < x; i++)

          cout << endl;

     }

 

 

 

 

 

 

 

e.   cin >> n;

     k = 1;

     m = n;

     do

     {

     j = 1;

       m = m * 2;

     do

     {

          .

          .

          j++;

 

       }while (j <= m);

     k++;

     }while(k <= n);

 

 

 

 

 

2.(5 points) To prove the following statement:

 

     3n³ + 2n = O(n³)

 

   Using the method discussed in class

 

 

 

 

 

 

 

 

 

 

3. (10 pts) Given an x, show that X⁶² can be computed with only eight multiplications (A general algorithm can not accomplish it).

 

 

 

 

 

 

 

4. (10 points) Assume that the input is a sequence of n real numbers. Design an algorithm that prints a number that is not in the sequence. Submit the program along with its output and the big-O notation (My algorithm runs O(n).

 

 

 

 

 

 

 

5. (10 points) Given an input set S containing n real numbers and a real number x. Design an algorithm that determines whether there are two numbers in S whose sum is exactly x. Submit your program and its time complexity analysis in terms of the big O.

 

 

 

 

 

 

 

 

 

 

 

6.(10 pts) Show the output of the following statement:

cout << func(5);

 

Int func(int n)

{

if (n == 0 or n == 1)

       return 1;

else

       return 2*func(n-2) + 3*func(n-1);

}

 

 

 

 

 

 

 

 

 

 

 

 

7.(10 pts) Consider the test function below:

 

Void test(int p1, int p2)

{

if (p1 != p2)

{

       p1 = p1 + 2;

       p2 = p2 - 1;

       test(p1,p2);

       cout << p1;

       cout << p2;

}

}

 

a)   Show the output resulting from the following function call: test(2,8).

 

 

 

 

b)   Is it possible that the execution may result in infinite recursion. If so, give an example.

 

 

 

 

 

7.(5 pts) Given a recurrence relation shown below, show the first 8 numbers of the sequence.

 

T(n) = 2(T(n-1) - 3* T(n-2))

T(1) = 1; T(2) = 4

 

 

 

 

8. (20 pts) Execute two java programs with O(n) and O(2ⁿ) time complexity respectively and submit the actual execution time and your programs.

 

     The input to the O(n) program:

          10,100,1000,10000,100000

 

     The input to the O(2ⁿ) program:

          1,10,20,30,40,50 .. until you give up

(more than 2 hours)

 

 

Type your answers and execute the programs. Submit their executions.