Instructions: In each of the five questions below, you are given a program fragm
ID: 3873768 • Letter: I
Question
Instructions: In each of the five questions below, you are given a program fragment. Estimate the running time for each program fragment in terms of n. Assume that the value of n is determined elsewhere in the program. You should make your upper bound and lower bound as tight as you can. Upper bounds that are too big and lower bounds that are too small will receive deductions during grading.
For each question:
1. State an upper bound on the running time of the program fragment using O( ) notation.
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 A
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 / 2 ; } } // ... in the main() function ... for (int i=0 ; i < n ; i++) { dothis(i) ; }
Question B
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(int x) { // function definition outside main() int something = 0 ; for (int i=0 ; i < x ; i++) { something++ ; } return something ; } // ... in the main() function ... int sum = n ; sum = sum + loop(3) ; sum = sum + loop(5) ;
Question C
for (int i=0 ; i < n ; i++) { int j = 2*i ; while (j < n) { j = j + 2 ; } }
Question D
t = 1 ; for (int i=0 ; i< n ; i++) { t = t++ ; } while ( t > 1 ) { t = t / 2 ; }
Question E
int sum = 0 ; int i = 1 ; while (sum <= n) { sum = sum + i ; i++ ; }
Explanation / Answer
As per Chegg policy, I am answering only first 4 subparts:
QA.) In best case, value of top can be less than 1. So, in best case, running time of given fragment is big-omega(n).
In worst case, while loop will run for log(top) times. There, it is O(n*log(top)).
QB.)function int loop will run for x times. So, depending on the values of x, we can have different running time.
But in case of given program fragment, big-omega(3) = O(5) = big-theta(1) i.e., best case.
QC.) Similarly, in this case, for loop will run n times while inner loop depends on the value of i i.e., inner loop runs
2+ 4+ ..+ 2(n) = n(n+1) = n2 times (approx.)
In this case, big-omega = big-oh = big-theta = O(n2).
QD.) for loop run n times to make the value of t as n+1 and while loop take log n times to make the value of t 1.
In this case, big-omega = big-oh = big-theta = O(n*log n).