Question

Q1. Determine the growth function and order of the following code fragment:

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

{

for (int count2=0; count2 < n; count2=count2*2)

{

System.out.println(count, count2);

}

}





Q2. What is the order of the following growth functions?

a. 10n2 + 100n + 1000

b. 10n3 – 7

c. 2n + 100n3

d. n2 log n





Q3. Arrange the growth functions of Q4 in ascending order of efficiency for n=10 and again for n = 1,000,000

Answer 1

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

{

for (int count2=0; count2 < n; count2=count2*2)

{

System.out.println(count, count2);

}

}

So, here growth function is $=n(2^0+2^1+2^3....2^n)$

Hence, order be $O(n \log n)$

2.

The order of the growth function are listed below -

a) $O(n^2)$

b) $O(n^3)$

c) $O(n^3)$

d) $O(n^2\log n)$

3.

Here

Initial value of n=10

and final value of n= 1000

If the for loop is is proceeding

 for(n=10;n=<1000;n++)
  print(n)

The resultant series will be 10, 11, 12, .... 1000

f(n) =n-10

here n=<1000

complexity O(n)