Please help me figure out how to do these questions I will give amazing ratings.

Question

Please help me figure out how to do these questions I will give amazing ratings. Answer exactly as the question prompt asks. You can ignore the PDF part I will do that on my own. Remember I'm going to need it for both LinkedList and ArrayList. Thank you. Part 2: Analyzing Running time for simple programs. You will practice your skills of estimating running time of code snippets. For each piece of code below, state the running time of the snippet in terms of the loop limit variable, n. You should assume that all variables are already declared and have a value. You should express your answer using Big-O or Big-O (Theta) notation, though your Big-O bound will only receive full credit if it is a tight bound. We allow you to use Big-O because it is often the convention to express only upper bounds on algorithms or code, but these upper bounds are generally understood to be as tight as possible. In all cases, your expressed bounds should be simplified as much as possible, with no extra constant factors or additional terms (e.g. O(n) instead of O(2n+5))

Explanation / Answer

1 ans)

The statements in the loop heading have fixed number of operations, hence they have constant running time O(1) when executed only once.

num=0;

The loop heading plus the loop body will give: O(n) + O(n) = O(n).
Loop running time is: O(n)

2 ans)

num=0;

for(i=1;i<=n*n;i=i+2) // i=1 ececutes only once O(1)

// i<=n*n executes n times O(n)

// i=i+2 executes n/2 times O(n/2)

// O(1)+O(n)+O(n/2)= O(n)

num++ //executes n times

The loop heading plus the loop body will give: O(n) + O(1) +O(n/2)= O(n).
Loop running time is: O(n)

3ans)

num=0

for(i=1;i<=n;i=i*2) // i=1 executes only once O(1)

// i<=n excutes n times O(n/2)

// i=i*2 executes n/2 times O(n/2)

// O(1)+O(n/2)+O(n/2) = O(n/2)

The loop heading plus the loop body will give: O(n/2) + O(n/2) +O(1)= O(n/2).
Loop running time is: O(n/2)

5ans)

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

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

num=num+i;

The running time for the operation num=num+i is a constant.

The outer loop runs n times. For the first execution of the outer loop the inner loop runs only once. For the second execution of the outer loop the inner loop runce twice, for the third execution - three times, etc. Thus the inner loop will be executed 1 + 2 + ... + (n-1) + n times.

1 + 2 + ... + (n-1) + n = n(n+1) / 2, which gives (n+1) / 2 on average.

Thus the total running time would be O(n*(n+1)/2) = O(n*n) = O(n2)

4ans)

num = 0;
for( i = 1; i <=100; i++)

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

num=num+i;

The running time for the operation num=num+i is a constant.

The outer loop runs 100 times. For the first execution of the outer loop the inner loop runs only once. For the second execution of the outer loop the inner loop runce twice, for the third execution - three times, etc. Thus the inner loop will be executed 1 + 2 + ... + (n-1) + n times.

1 + 2 + ... + (n-1) + n = 100(n+1) / 2, which gives (n+1) / 2 on average.

Thus the total running time would be O(100*(n+1)/2) = O(n*n) = O(n2) (say 100 as n)

6ans)

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

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

num=num+i;

The running time for the operation num=num+ i is a constant.

The outer loop runs n times, The nested loop runs and incrented n * 2 times, hence the complexity would be
O(n3)

7ans)

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

num++;

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

num++;

First, we asume that the running time to compute an arithmetic expression without function calls is negligible. Then, we have two consecutive loops with running times O(n) and O(n). We take the maximum complexity, hence the overall runing time would be O(n)

8ans)

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

num++;

The for loop iterates <2500 times i.e 2499 times. so that the time complexity for the above loop is O(2499)

say 2499 = n. So that running time is O(n)

9ans)

for(i=n-1;i>0;i--)

{

Maxpos=i;

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

{

if (a[j]>a[Maxpos])

Maxpos=j;

}

exchange(i,Maxpos);

}

The running complexity for the above program is O(n2).

this is a pseudo code for insertion sort algorithm.

The insertion sort algorithm reprresents the time complexity as O(n2).

10ans)

for(i=n;i>0;i=i/2)

{

for(j=i;j>0;j=j/2)

{

//constant time operations

}

}

The first outer loop executes n/2 times and inner loop also excutes n/2 times.

So that the time complexity for running the above code is O(n/2)+O(n/2)= O(n/2) (average case).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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