Which of the following statements about running times of algorithms is correct?
A)When determining the running time, lower-order terms must be taken into consideration.
B)When determining the running time, constants are not taken into consideration.
C)An algorithm that is O(1) means that only one comparison takes place.
D)An algorithm that is O(n) means that the number of comparisons does not grow as the size of the array increases.

Question

Quizplus · Accepted Answer

When determining the running time of an algorithm, the constants are not taken into consideration, only the dominant term or highest power of n. The lower-order terms do not significantly affect the growth rate of the algorithm as n becomes large. Option A is incorrect as lower-order terms are dropped in order to simplify calculations. Option C is incorrect because O(1) means that the algorithm takes a constant amount of time to run, not necessarily that only one comparison is done. Option D is incorrect because an algorithm that is O(n) means that the number of operations grows linearly with the size of the input, i.e., as the size of the array increases, the number of comparisons will increase as well.

Which of the Following Statements About Running Times of Algorithms