← BIT 201 Data Structures and Algorithms
Sorting, Searching and Big-O Notation
Notes
Comparing algorithm growth
An algorithm is a defined sequence of steps for solving a problem. Big-O notation describes an asymptotic upper bound on resource growth as input size increases, rather than predicting exact seconds. Constant time, O(1), does not grow with input size under the assumed model. Linear time, O(n), grows proportionally; quadratic time, O(n squared), can grow much faster. Always identify whether a statement concerns worst-case, average-case or amortised behaviour, and consider memory consumption alongside execution time when selecting an algorithm for a business workload.
Sorting and searching choices
Linear search checks entries sequentially and works on unsorted data. Binary search repeatedly halves a sorted search interval, requiring O(log n) comparisons with efficient indexed access. Sorting therefore has a preparation cost that may be worthwhile for repeated searches. Insertion sort builds a sorted prefix and can perform well on small, nearly sorted inputs, although its worst case is quadratic. Merge sort divides and combines data in O(n log n) time and generally needs auxiliary storage. Stable sorting preserves the original relative order of records with equal keys.
Practical example
An Eldoret agribusiness cooperative stores 1,024 farmer identifiers in an indexed array. A failed linear search may inspect all 1,024 entries. Once sorted, binary search takes at most about 11 comparisons using a standard inclusive-bound implementation. If a quadratic sorting workload doubles from 1,000 to 2,000 records, its leading operation count grows by approximately 2 squared = 4 times, not twice. For daily repeated farmer lookups, sorting once can therefore repay its cost. For one lookup in a tiny unsorted list, linear search may avoid unnecessary preparation and remain the simpler choice.
Quiz
1. What must hold before binary search can safely search an array by identifier?
2. If a quadratic leading cost dominates, doubling input gives approximately what cost multiplier?
3. What does stable sorting preserve?
Sign in to submit and securely grade your quiz.