Exercise 1: Best and Worst Case for Sorted-Array Insertion — Possible Solution
====================================================================

BEST CASE: INSERTING AT THE END
------------------------------
If the new element belongs at the very end of the array, no existing
elements need to shift at all - the new value is simply placed in the
next free position. This requires a constant, fixed amount of work
regardless of how large the array already is:

  Best case: Theta(1)

WORST CASE: INSERTING AT THE BEGINNING
------------------------------
If the new element belongs at the very beginning, every single one of
the n existing elements must shift over by one position to make room
for it. The amount of shifting work grows directly in proportion to
how many elements are already in the array:

  Worst case: Theta(n)

WHY THEY DIFFER
------------------------------
Per this chapter's own best/worst-case distinction, these two figures
describe genuinely different INPUT SCENARIOS for the exact same
insertion operation - not different algorithms. The amount of work
this operation actually requires depends entirely on WHERE in the
array the new element needs to go: no shifting at all at one extreme
(the end), maximal shifting at the other (the beginning). The
underlying insertion code is identical in both cases; only the
position of insertion changes how much work it does.

WHY THIS WORKS AS AN ANSWER
------------------------------
Both cases are analyzed using this chapter's own count-the-operations
approach (from Chapter 3), stated in the correct Theta notation this
chapter itself introduces, and the difference between them is
explained as a difference in input scenario per this chapter's own
best/worst-case distinction, rather than treated as two separate
algorithms.