Question

1. Be able to determine the runtime complexity of:

1. A Java assignment statement
2. A single loop
3. Nested loop

2. Given that for any polynomial of degree n, p(x) = a_nxⁿ + a_n-1 x^n-1 + …a₁x + a₀, p(x) = O(xⁿ).              Show that:            an expression such as the following                                                              

4x³ + 7x² + 12 is O(x³), by finding the witnesses, C and k.     

3. Which of the following statements are true?                                             

1. The running time of a loop is, at most, the running time of the statements inside the loop times the number of iterations.  
2. Consider the Java statement:

            int x = 250;

This statement has time complexity of T(n) = O(1).                           

3. Consider the Java statement:

            int x = 250;

This statement has time complexity of T(n) = O(n).

Answer 1

Be able to determine the runtime complexity of:

1. A Java assignment statement :

Run time complexity is O(1)

2. A single loop

Run time complexity = no of iterations * complexity of statements inside loop

3.Nested loop

As said earlier for a single loop. Iteratively apply the same.

For k loops,

Run time complexity = no of iterations in loop1 * no of iterations in loop2 *.... No of iterations in loopk * complexity of statements inside loop1*complexity of statements inside loop2*.....*complexity of statements inside loopk

4. Given that for any polynomial of degree n, p(x) = a_nxⁿ + a_n-1 x^n-1 + …a₁x + a₀, p(x) = O(xⁿ).

Show that: an expression such as the following 4x³ + 7x² + 12 is O(x³), by finding the witnesses, C and k.

To find the witness we have run loop. As the highest degree of the polynomial is 3 here. We have to run 3 iterations of size n inorder to determine the c and k.

So, Run-Time complexity = O(x^3)    

5.Which of the following statements are true?         

                                    

1. The running time of a loop is, at most, the running time of the statements inside the loop times the number of iterations.  
2. Consider the Java statement:

            int x = 250;

This statement has time complexity of T(n) = O(1).                           

     3. Consider the Java statement:

            int x = 250;

This statement has time complexity of T(n) = O(n).

Among the statements the Statement 1 and 2 are correct. For example see the example of the loop given below.

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

// … Statements of 0(1)

}

Complexity of this loop is = O(n) = no of iterations * complexity of statements

= O(n) * O(1)

As we know that assignment statement complexity is O(1) not O(n).