Final answer:
Option d, 10n + 25, is the formula that represents O(n), as its operation count grows linearly with the size of the input n.
Step-by-step explanation:
The goal is to determine which of the following formulas is O(n), where the notation O(n) refers to an asymptotic upper bound for the complexity of an algorithm, meaning the operation count grows linearly with the input size n. The options are:
- a. 16n3
- b. n2 + n + 2
- c. n2/2
- d. 10n + 25
Looking at the options, we can rule out a and c because these are polynomially bounded by n3 and n2 respectively, which are of higher degree than n. Option b is also not linear, since it contains an n2 term. Thus, the formula that is O(n) is option d, 10n + 25, since its highest degree term with respect to n is 1, fulfilling the condition for being O(n).