Consider the following code fragment: for (i = 4; i < n; i++) for (j = i-3; j <=
ID: 3542603 • Letter: C
Question
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, use summation form for each loop ( ? ), and show your work for both part (a and b), dont leave anything missing. thank you
Explanation / Answer
1)The outer loop will start from 4 and go till n-1..the inner loop will run 7 times..(i-3 to i+3) in each iteration...
so the total number of times statment gets excuted is (n-1-4)(7)= 7(n-5)
2)In The outer loop if i=1 then inner executes -2 to n i.e n+3 times
if i=2 -1 to n i.e n+2 times
and so on if i=n-1 n-4 to n i.e 5 times
therefore the total times is 5+6+7+8+................+(n+2)+(n+3)
3)incrementing 2 at a time
if n=1, inner and outer each will executes 1 time
if n=2 inner and outer each will executes 2 time
n=3 => 2 times ,,this alue is incremented only if n value is next power of 2
if n=4 each => 3 times
n=4 each 4 times,,,it is following a pattern where each loop executing (logn to the base 2) +1
so total executions id [(logn to the base 2) +1]*[(logn to the base 2) +1]
4) for i=1 it executes (n-2)(n-1)2
i=2 => (n-3)(n-2)3
and so on i=n-2 => 1.2.(n+1)
so total executions summation of (n-k)(n-k+1)k
where k ranges from 2 to (n+1)
the big oh complexity in 1st and 2nd case is n^2
In 3rd case it is O[(logn to the base 2) +1]^2 ,,,,in 4th, the complexity is n^3 since we are using 3 loops.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.