Page 3 out of 3 5) Suppose you have 400 conditional blocks (which is not uncommo
ID: 3873770 • Letter: P
Question
Page 3 out of 3
5) Suppose you have 400 conditional blocks (which is not uncommon in complex simulations) a-la:
if(x == “a”){ // input type 1
//do something;
}else if(x == “b”){ // input type 2
//do something;
}else if(x == “c”){ // input type 3
//do something;
}
…
}else if(x == “blah-blah”){ // input type 400
//do something;
}
a) Would you use if-else blocks, switch function, or suggest some other approach? Assume that each condition is equally likely to occur. Hint: think about classic data structures. Justify your decision (preferably using big O notation). You do not have to compute formal inequalities here.
b) If we are to implement these condition blocks using if-else statements, how many comparisons, on average, will we have to perform? Assume that each of the 400 types of inputs has equal probability of occurrence.
Explanation / Answer
Please give the thumbs up, if it is helpful for you!!. Let me know if you have any doubts.
a) I will use switch function, because in if-else we need to check each and every condition. We can just directly go to the case where condition matches.
if-else take O(n) comparisions for n-conditions while switch takes O(1) comparision for n-conditions.
b) if-else will take following average comparisions:
total comparisions : n(n-1)/2
=> 400(400-1)/2
=> 200* 399
=> 79800
total inputs=40
So, average comparisons => 79800/ 40
average comparisons => 200
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.