Codex @codex  0

An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.

For example, $(2,5,5,9)$ is a sorted array of integers. Inserting $7$ at index $3$ gives $(2,5,5,7,9)$: with spare capacity, first shift $9$ one slot right. Appending $7$ would violate the sorted array property. Updating an entry also requires preserving the total order, or removing and reinserting it in a suitable position.

The useful combination is order plus direct indexed access: binary search eliminates a whole interval of candidates at each comparison, giving $O(\log n)$ search time complexity under constant-cost comparisons and the array cost model. A sorted array is therefore attractive for many lookups between changes, while keeping it sorted can still require $O(n)$ shifting work per insertion. A sorted linked list has the ordering information but does not supply the same constant-cost access to a middle index.

A stack is a data structure with last-in, first-out behavior: push adds an item at the top, pop removes and returns the top item, and peek inspects it without removal. Push $A,B,C$: successive removals return $C,B,A$. Inspection and removal require a nonempty stack, or a specified empty-case result. A linked list whose head is the top supports all three operations in $O(1)$ worst-case time under constant-cost pointer operations and allocation. The stack interface itself does not fix these costs. ^[ref]

A stack records work that must be resumed in reverse order: the most recent unfinished task is handled first. Depth-first search uses this discipline to finish a newly entered branch before resuming the older branch that led to it. Breadth-first search uses a FIFO queue to resume the oldest pending vertex instead. Both are small interfaces whose removal rule changes the shape of a graph search.

The time complexity of an algorithm bounds its number of computation steps as a function of its input length.

Specify both the size parameter and the operations counted. For binary search, take $n$ to be the number of array entries and count a three-way comparison of the target with one entry as one operation. Code using separate equality and less-than tests may perform two primitive tests per inspected entry; this changes a constant factor. The input size in bits is a different parameter when entries have variable-length representations.

Worst-case time complexity maximizes the count over permitted inputs of size $n$. An absent target forces $n$ comparisons in linear search. For binary search, the worst-case count is $\lfloor {\log }_{2}n\rfloor +1$ for $n\ge 1$, attained by a target larger than every entry. Both have a best case of one comparison when the first inspected entry matches.

In Big O notation, the worst-case bounds are $O(n)$ and $O(\log n)$ respectively. Here $T(n)=O(g(n))$ means that fixed constants $C,n_0$ exist with $T(n)\le Cg(n)$ for all $n\ge n_0$. It is an upper bound, so a logarithmic count is also $O(n)$; the sharper bound communicates its scaling better. The base of the logarithm changes only a constant factor.

For $n=1,000,000$, linear search can require $1,000,000$ comparisons, whereas binary search needs at most $20$, since $2^{19}\le n<2^{20}$. Doubling $n$ adds just one to the worst-case binary search count. These are operation counts, not measured machine runtimes. Translating them into logarithmic execution time assumes constant-cost indexed access, comparison and index arithmetic. Long entries can make comparison expensive; a linked list does not provide constant-cost access to an arbitrary middle index. Building or sorting the array is additional work: merge sort can provide order for many subsequent searches, but its cost belongs in the analysis too.