Estimate the running time for the following program fragment in terms of n. Assu

Question

Estimate the running time for the following program fragment in terms of n. Assume that the value of n is determined elsewhere in the program. Make your upper bound and lower bound as tight as you can. Please answer the following 1. State an upper bound on the running time of the program fragment using notation. 2. Briefly justify your upper bound. State a lower bound on the running time of the program fragment using notation. 3. 4. Briefly justify your lower bound. Even in cases where the upper bound and lower bound are the same function, the justifications would be different. (For upper bounds, you are claiming that the code will run no slower than the upper bound. For lower bounds, you are claiming that the code will take at least that amount of time.) Question 1: In this question, the program fragment resides in the main ( ) function. The program fragment calls a function loop).In your running time estimates, include the time to execute the program fragment in main) and the time to execute the function calls. int Loop (inx) { // function definition outside main() iat something something++i 7... in the main) function .. . int sumni umum+loop (3)

Explanation / Answer

Upper Bound: Big O notation: It is a time complexity where for every n, f(n)=0(g(n)),

g(n)>=f(n).

Lower bound (): It is a time complexity where for every n,f(n)=(g(n)),

f(n)>=g(n).

1.Upper bound for the above code fragment: O(n).

2. Justification for upper bound:

When loop(3) is called : Outer function call runs constant time i.e 1 time and inner for loop runs n time.

So, overall complexity = 1. n= O(n).

Same will apply to loop(5) or with any other integer value of n.

3. Lower Bound : (n)

4. Justification for lower bound:

5. With any value of n, Complexity will remain same because outer function call will take constant time and inner for loop will runs n time.

So, overall complexity will be (n).

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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