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

Sol:

PART-I

Runtime Complexity: The runtime (or) time complexity of an algorithm is the amount of execution time taken by the program for a given input of size(n). The time complexity of an algorithm is defined as the number of times the program statements are executed. This is also known as "Frequency Count f(n)".

Section:1. The Time complexity of a Java assignment statement: The assignment statement in any programming language is executed only once i.e frequency count =1 or assignment statement takes one unit of time. With Big-Oh Notation, It is expressed as

T(n)=O(1)

Section 2: Time complexity of a Single for loop: Consider the following Single java "for loop" example

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

{

System.out.println("i="+i); //Printing the value of "i"

}

Let us break down the for loop in to number of parts to find frequency count of every part

a) Loop initialization variable "i=0" is executed only once ,there fore ------> f(n) =1

b) Loop condition is executed  "n+1" times i.e "n" times for condition "True" & "1" time for condition"False",there fore -----> f(n) =n+1

c) Print statement inside loop is exceuted "n" times because for loop is repeated for "n" times,there fore -----> f(n) =n

d) Loop updation statement "i++" is exceuted "n" times,therefore -----> f(n) =n

Together total frequency count f(n) = 1+n+1+n+n =3n+2

If the frequency count is "3n+2",we can ignore the foloowing

• The constant line "2" in "3n+2"
• The leading multiplies like "3" in "3n

So we can represent final frequency count f(n) = n , With big-Oh notation T(n) = O(n)

Section 3:Time complexity of a Nested for loop: Consider the following java "Nested for loop" example

for(i=0 ; i<n ;i++) --------------->frquency count of outer for loop 2n+2

{

for(j=0 ; j<n ;j++) --------------->frquency count of inner for loop 2n+2

{

System.out.println("i="+i",j="+j); //Printing the value of "i,j" -------->frquency count n

}

}

• Inner for loop total frequency count is given as =1+n+1+n+n =3n+2
• Outer for loop total frequency count is given as =2n+2

Together total frequency count f(n) = (2n+2)(3n+2) =6n²+4n+6n+4 = 6n²+10n+4

• Ignoring constant like "4" ,the remaining equation is 6n²+10mn
• Ignoring 10n,because 10n is grow less , when compared to 6n²,the remaining equation is 6n²
• Ignoring leading multiplies like "6" ,the remaining equation is n²

So we can represent final frequency count f(n) = n²

With big-Oh notation T(n) = O(n²)

PART-II

• Big Oh Notation:According to big Oh notation "f(n) = O(g(n)), where f,g are two non negative integers function there exists C,k constants such that f(n) <= C.g(n) n >= k and C>0"
• The simple meaning is function g(n) start grawing faster than f(n) at particualr C,k values
• Given 4x³ + 7x² + 12 is O(x³), by finding the witnesses, C and k.   

Let us consider f(n) = 4x³ + 7x² + 12 & g(n) = O(x³)

Case1: Consider C=1 & k=1 then according to Big Oh notation ,Here "k" is the value of "x" chosen for one particular case

• 4(1)³+7(1)²+12 <= 1.(1)³
• 4+7+12<= 1
• 23<=1 --> False

Therefore Case1 Failed

Case2: Consider C=5 & k=2 then according to Big Oh notation

• 4(2)³+7(2)²+12 <= 5.(2)³
• 32+28+12<= 40
• 72<= 40 --> False

Therefore Case2 is also Failed

Case3: Consider C=10 & k=2, then according to Big Oh notation

• 4(2)³+7(2)²+12 <= 10.(2)³
• 32+28+12<=80
• 72<= 80 --> True

At C=10 and k=2 funtion g(n) grows faster than f(n)

Therefore witness is C=10 & k=2

PART-III

a) According to Section2, Statement inside for loop are executed “n” times, if for loop is iterated n+1 times

Ans :YES

b) According to Section1 Java statement: int x = 250; time complexity is O(1)

Ans :YES

c) According to Section1 Java statement: int x = 250; time complexity T(n)=O(n) is wrong

Ans :No