(From Weiss \"Data Structures and Algorithm Analysis in Java, 3rd Edition\", Sho

Question

(From Weiss "Data Structures and Algorithm Analysis in Java, 3rd Edition", Shortened Problem #2.7)

For each of the program fragments, give an analysis of the running time (Big-Oh, show work):

(1)

sum = 0;

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

sum++;

(2)

sum = 0;

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

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

sum++;

(3)

sum = 0;

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

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

sum++;

...

And two other questions I had on a previous test and got wrong.

(1)

The answer is n+1 but I don't know why.

int sum = 0;

for (int i = n; i>0; i=i-2)

sum+=i;

(2)

Find the reccurance relation that accurately describes the amount of work needed by the below algorithim assuming the basic operations counted are *, +, and -. Also, find the complexity. Explain why the answers are correct.

(Answer is "T(n)= 4+ T(n-1) , T(1) =0" for the relation, and "O(n)" for the complexity)

mystery(n){

if(n==1)

return 1;

else

return 2*n + mystery(n-1) -1;}

Explanation / Answer

Please rate with 5 stars :)

1. O(n) since there is only 1 loop

2. O(n^2) since there are 2 loops

3. O(n^2) since there are 2 loops

Other questions:

1. This sums up integers leaving one integer in between.

Consider n=10;

This loop does this :

10+8+6+4+2 = 30.

For solving recurrances, you can use either the Master Theorem or substitution.

Cheers!

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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