PROBLEM-5 analysis (10 points): Below is a C function operating on an array of l
ID: 3724610 • Letter: P
Question
PROBLEM-5 analysis (10 points): Below is a C function operating on an array of length n. It does some weird computation. .. Your jobs: (A) Determine a tight worst-case runtime bound for the function. Explain your reasoning and describe a scenario in which this worst-case is achieved. (B) Do the same exercise as (A), but now for the best-case runtime. REMEMBER: "Tight" means you are looking for a big- runtime bounds. Both questions are for arbitrary n. For example, the answer to (B) is not "the best case is when n=0" int do stuff (int all, int n) int i, j, x: x=0 ; for (i=0; i
Explanation / Answer
A) The tight worst case run time bound here will be the even part where we are checking whether the array element is even or not.
-> here the worst case will be when all the array elements will be even for eg. {2,4,6,8,10} here n = 5 then,
every time the condition if(a[i]%2 == 0) will be true and therefore the inner loop
for(j=0;j<n;j++){
x+=a[j];
}
will run.
-> hence for each element of array it ( inner loop ) will run n times making the total complexity
of the function O(n2) .
-> this will be the worst case run time bound for the function.
B) The tight best case complexity will be when the array will contain all the odd elements for eg. {1,3,5,7,9} here n=5 then,
-> here the function control will directly come to the else part
else {
x-=a[i];
}
-> and thereby the complexity will be O(n) because only the outer for loop
for(i=0;i<n;i++) {
will run .
Note : This can be generalised for any arbitrary n whether n = 0 or n >0 .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.