Question about big-o notation complexity. Consider the following code fragment:

Question

Question about big-o notation complexity.

Consider the following code fragment:

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

  for (j = i-3; j <= i+3; j++)

    Statement 1;

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

   for (j = i-3; j <= n; j++)

     Statement 2;

for (i = 1; i <= n; i=i*2)

    for (j = 1; j <= n; j=j*2)

      Statement 3;

for (i = 1; i < n-1; i++)

   for (j = i+1; j <= n; j++)

    for (k = 1; k <= j; k++)

                   Statement 4;

a) Find the exact number of times Statement 1, 2, 3, and 4 get executed. You must show the details of your computations.

b) Determine the big-O complexity of this code fragment.

Please show the work, so i can understand what's going on. and both parts (a & b).

Explanation / Answer

1st

the outer loop will start from 4 and go till n..the inner loop will run 6 times..(i-3 to i+3) in wach iteration...

so the total number of times statment gets excuted is (n-4)(6)

2nd

the outer loop will work n times. the inner loop will work (n+3) times since j=i-3

so statement 2 will execute n(n+3) times

3rd

the outer and the inner loop will run n times the statment will be executed log[(n)(n+3)] times [ we are using log since the increment is getting twice each time)

4th

i loop will run n times, j loop will run n times...k loop running value depends on j value..it wud b 1,2,3,4, and so on...

so the total number of times atatement gets executed will be ...n*n*n!

the big oh complexity in 1st and 2nd case is n^2(since there are too loops involved)).

In 3rd case it is 2log(n)[since the increment is getting twice each time]. in 4th, the complexity is n^3 since we are using 3 loops.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.