An algorithm that tests whether the first array element is equal to any of the other array elements requires at most n - 1 comparisons, where n is the number of array elements. Which of the following statements is false?
A) If the array has 10 elements, this algorithm requires up to nine comparisons.
B) If the array has 1000 elements, it requires up to 999 comparisons.
C) As n grows larger, the n part of the expression n - 1 "dominates," and subtracting 1 becomes inconsequential. Big O is designed to highlight these dominant terms and ignore terms that become unimportant as n grows.
D) An algorithm that requires a total of n - 1 comparisons is said to be O(n - 1) and is said to have a linear run time.

Question

Quizplus · Accepted Answer

The false statement is D because the Big O notation simplifies n - 1 to O(n), indicating linear time complexity without specifying the subtracted constant, as constants are considered non-dominant terms in Big O notation.

An Algorithm That Tests Whether the First Array Element Is