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

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: State an upper bound on the running time of the program fragment using notation I. 2. Briefly justify your upper bound. 3. State a lower bound on the running time of the program fragment using notation. 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(O function. The program fragment calls a function dothis (). In your running time estimates, include the time to execute the program fragment in main () and the time to execute the function calls. void dothis(int top) // function definition outside main () while (top > 1) top top 2i .in the main) function for (int i=0 ; i

Explanation / Answer

If you consider the main loop, you can see that we are running the for loop for n times.

Now inside the loop, we are calling dothis method which is dividing the n by 2 every time. So, to calculate the upper bound, lets think it this way that the dothis method's while loop won't run more than n times anyways. Therefore the upper bound becomes O(n * n) i.e. O(n2)

Now, to calculate the lower bound i.e. a tighter bound, lets look at the dothis method more closely. We need to see that how many times is the while loop run. So, first time n is n, it gets reduced to n/2 after this run. Second time it starts from n/2 and gets reduced to n/4 after the run. Third time..... n /8...... Finally 1. So, in short it is something like n, n/2, n/4, n/8, n/16..... 1 which if you see is log(n) steps. So, a tighter bound for this method is log(n). So, the total time here is Big Omega(n * log(n)) i.e. Big Omega(nlog(n))

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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