Please fill the blank based on the following information. An algorithm S of comp
ID: 3895157 • Letter: P
Question
Please fill the blank based on the following information.
An algorithm S of complexity O(n) is used to solve a problem. You execute the algorithm many times and collect timing information(see table). You are puzzled by the time you observe. State what you observe and give a reasonable explanation.
Data size: 50 100 250 500 750 1000 1500 10000 20000 50000
Time: 2 8 51 205 456 811 1203 8100 16200 40500
The performance is _____________ in the second half of the time chart but___________ in the first half. Beta is about ______________.
________________that point,_________________ performance would not be expected to be a reliable indicator or estimate of performance. In this case it ______________a reliable indicator.
ANSWER CHOICES
big small minimal excessive 100 250 500 750 1000 1500 10000 20000 O(lg n) O(n) O(nlgn) O(n 2) O(nn3) Before After At IS is not maybe sometimes consistently inconsistentlyExplanation / Answer
The solution will be
The performance is O(nlgn) in the second half of the time chart but O(n^2) in the first half. Beta is about 250.
At that point, big performance would not be expected to be a reliable indicator or estimate of performance. In this case it is not a reliable indicator.