Why Some Algorithms Win: Big-O for Search and Sort

Hi, I'm Byte. Imagine you must find one name in a list. With LINEAR SEARCH you check items one by one from the start. In the worst case the name is last, or missing, so you make about n checks for a list of size n. We write that growth as O(n): double the list, roughly double the work. If the list is already SORTED, BINARY SEARCH is far faster. You look at the middle item; if your target is smaller you throw away the upper half, if larger you throw away the lower half. Each step halves what's left, so you finish in about log2(n) checks: that is O(log n). A list of one million sorted items needs only about 20 checks! But here is the catch about CORRECTNESS: binary search only works if the list is sorted. On unsorted data it can throw away the half that actually holds your target and report 'not found' even when the item is there. Correct means 'always gives the right answer'; efficient means 'does it with little work'. A good algorithm must be both. Sorting itself costs time. BUBBLE SORT makes repeated passes through the list, swapping adjacent neighboring pairs that are out of order, until no swaps remain; it runs in O(n^2) in the worst case. INSERTION SORT works differently: it takes each unsorted element and walks backward through the already-sorted prefix, shifting items along until it finds the right slot to insert — also O(n^2) in the worst case, but by a different mechanism. Smarter sorts like merge sort run in O(n log n), which scales much better for large lists. Big-O describes how runtime GROWS with input size, ignoring small constants and tiny inputs. Slower-growing wins as data gets big: O(1) is best, then O(log n), O(n), O(n log n), and O(n^2) is the worst of these. If you ever feel stuck, just ask yourself one question: 'how many steps for a list of size n, in the worst case?'