Answer to Question #243551 in Algorithms for kofi

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. 10n² + 100n + 1000

b. 10n³ – 7

c. 2n + 100n³

d. n² 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

1.

The outer loop runs n times.

The inner loop runs 1 time if n=1..2, 2 times if n=3..4, 3 times if n is upto 8, 4 times if n is upto 16, 5 times if n is upto 32.

So, the growth function:

$f(n)=nlog_2n$