Estimating running time of code snippets. For each piece of code below, state th

Question

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. Express your answer using Big­O or Big­? (Theta) notation, though your Big­O bound will only receive full credit if it is a tight bound. 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))

[PLEASE PROVIDE RUNNING TIME AND EXPLANATION!]

Explanation / Answer

1.

for(int i=0;i<n;i+=2) // Since it runs for n/2 times its complexity is O(n)

sum++; // Since it runs for every bvalue of i its complexity is O(n)

Therefore overall complexity is O(n)

2.

for(int i=1;i<n;i*=2) // Since i value grows logarithmically so times its complexity is O(logn)

sum++; // Since it runs for every bvalue of i its complexity is O(logn)

Therefore overall complexity is O(logn)

3.

for(int i=0;i<n;i++) // Since it runs for n times its complexity is O(n)

for(int j=0;j<n;j++) // Since it runs for n times its complexity is O(n) but in the whole progam it runs for every value of i so its overall complexity is O(n2)

sum++; // Since it runs for every value of i its complexity is O(n2).

Therefore overall complexity is O(n2)

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

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