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 OO notation 2. Briefly justify your upper bound. 3. State a lower bound on the running time of the program fragment using 20O 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 () 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 / I... in the main) function for (int 0

Explanation / Answer

void dothis(int top){

while (top>1)
{
top=top/2;
}}

i=0
n-5

i=0 top=0.5
i=1 top= 1

the worst-case runtime complexity of the algorithm is considered as the maximum number of steps taken to complete task.
the best-case runtime complexity of the algorithm is considered as minimum number of steps taken to complete the task.

Basically we divide complexity as one of the below

1. Constant
2.Logarthmic
3.Linear
4.linearithmic
5.Quadratic
6.Cubic
7.exponential

The program which we have is linear function. hence We use big-O notation for asymptotic upper bounds, since it bounds to grow with the running time from above for large input sizes.

O (n)

2. We use Omega notation for asymptotic lower bounds since it bounds to grow with the running time from above for large enough input sizes.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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