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 grows with input size in the worst case. For an unsorted array, searching may require checking every element, so the time grows linearly with n, which is O(n). Appending to a dynamic array is typically O(1) on average because most appends just place the item at the end; occasional resizes to accommodate more elements cost O(n) but that cost is spread across many insertions, giving an amortized O(1). Inserting at the beginning forces shifting all existing elements one position to make space, which takes time proportional to n, so O(n). This combination—worst-case growth for search, amortized constant time for end insertion, and linear time for beginning insertion—accurately describes the common array operation costs.

Big-O describes how the running time grows with input size in the worst case. For an unsorted array, searching may require checking every element, so the time grows linearly with n, which is O(n). Appending to a dynamic array is typically O(1) on average because most appends just place the item at the end; occasional resizes to accommodate more elements cost O(n) but that cost is spread across many insertions, giving an amortized O(1). Inserting at the beginning forces shifting all existing elements one position to make space, which takes time proportional to n, so O(n). This combination—worst-case growth for search, amortized constant time for end insertion, and linear time for beginning insertion—accurately describes the common array operation costs.