Which statement describes Big-O for common array operations correctly?

Which statement describes Big-O for common array operations correctly?

• A. Big-O describes average-case growth; search in an unsorted array is O(log n);
• B. Big-O describes worst-case growth; search in an unsorted array is O(n); insert at end is O(1) amortized; insert at beginning is O(n) due to shifting.
• C. Big-O describes best-case growth; all operations are O(1).
• D. Big-O is a measure of memory usage.

Answer: (B)

Big-O describes how the running time or space usage grows as the input size increases, typically focusing on the worst-case scenario for an operation. For common array operations, this framework helps compare how different actions scale as n becomes large.

Searching an unsorted array in the worst case must examine every element, since you have no order to guide the search, so the time grows linearly with n. That gives O(n). Inserting at the end can be done in constant time when there’s available capacity; with dynamic arrays you might resize occasionally, but those expensive resizes are amortized over many insertions, resulting in amortized O(1) time per insert. Inserting at the beginning, however, requires shifting all existing elements one position to the right to make room at the start, which takes time proportional to n, or O(n).

The idea that Big-O is about average or best-case growth isn’t correct here, and describing Big-O as a measure of memory usage isn’t precise either—Big-O can describe time or space growth, but the common emphasis in these statements is on worst-case time. The described behaviors—unsorted search being O(n), end insertion being amortized O(1), and beginning insertion being O(n) due to shifting—are the correct way to frame Big-O for these array operations.