An algorithm is a finite, unambiguous procedure that solves a class of problems. This section covers what makes something qualify as an algorithm, two fundamental search strategies (linear and binary), and two elementary sorting algorithms (bubble sort and insertion sort), including how to count their comparisons and swaps in best and worst cases.
Difficulty: Introductory | Prerequisites: arrays, basic loop logic, Big-O notation
Searching and sorting are the bread and butter of algorithm design. Nearly every non-trivial program does one or both. Understanding the properties that every algorithm must have gives you a framework for evaluating whether a procedure is well-defined. Knowing bubble sort and insertion sort, along with their comparison and swap counts, prepares you both for exam questions and for understanding why more advanced algorithms (merge sort, quicksort) exist.
Algorithm
A finite sequence of well-defined instructions for solving a class of problems or performing a computation. Think of it as a recipe that always terminates and always gives the right answer for any valid input.
Linear search
A search method that checks each element of an array one by one, from first to last, until it finds the target or reaches the end. Simple but slow for large arrays.
Binary search
A search method for sorted arrays that repeatedly halves the search space by comparing the target to the middle element. Much faster than linear search, but requires the array to be sorted first.
Bubble sort
A sorting algorithm that repeatedly walks through the list comparing adjacent elements and swapping them if they are out of order. Called "bubble" because larger elements gradually rise to the end of the array.
Insertion sort
A sorting algorithm that builds a sorted portion one element at a time, taking each unsorted element and placing it in its correct position within the already-sorted section.
Comparison (in sorting context)
An operation where two elements are checked against each other to determine their relative order.
Swap
An operation where two elements exchange positions in the array.
Every algorithm must satisfy all five:
Input: takes values from a specified set
Output: produces output values (the solution) for each set of inputs
Correctness: produces the correct output for every valid input
Effectiveness: every step can be performed exactly, in finite time
Finiteness: terminates after a finite number of steps for any input
Generality: works for all problems of the desired form, not just a specific instance
The problem: determine whether a given element x is in a sorted array A. Return the index if found, or -1 if not.
Linear search
Walk through the array element by element.
Stop when x is found or the end is reached.
Worst case: O(n) comparisons (element is last or absent).
Best case: O(1) (element is first).
Binary search
Compare x with the middle element of the current range.
If equal, done. If x is smaller, search the left half. If larger, search the right half.
Worst case: O(log n) comparisons.
Requires the array to be sorted beforehand.
Sorts n elements into non-decreasing order. Elements may not be unique.
The basic operation compares adjacent elements a_j and a_(j+1).
If they are out of order, swap them.
Repeat passes over the data until no swaps are needed.
Best case (already sorted):
Comparisons: n - 1
Swaps: 0
Worst case (sorted in reverse):
Comparisons: n² - n
Swaps: (1/2)n² - (1/2)n
Both comparisons and swaps are bounded by a quadratic term, so bubble sort is O(n²).
Also sorts n elements into non-decreasing order.
Maintain a sorted portion at the front (initially just the first element).
Take the first element of the unsorted portion and insert it into its correct position in the sorted portion.
Repeat for positions 2 through n - 1.
Best case (already sorted):
Comparisons: n - 1
Swaps: 0
Worst case (sorted in reverse):
Comparisons: (1/2)n² - (1/2)n
Swaps: (1/2)n² - (1/2)n
Like bubble sort, insertion sort is O(n²) in the worst case. In the best case, both run in O(n), but insertion sort tends to perform fewer swaps on average.
Students sometimes think binary search works on unsorted arrays. It does not. The array must be sorted first, or binary search gives incorrect results.
Bubble sort and insertion sort have the same worst-case complexity, O(n²), but they are not identical in behaviour. Insertion sort generally does fewer swaps on partially sorted data.
"Finiteness" does not mean "fast." An algorithm can be finite and still take an astronomically long time. Finiteness just means it terminates.
Students sometimes confuse the best case with the average case. Best case is the most favourable possible input (typically already sorted for these algorithms). Average case is a separate analysis.
⚠️ You may be asked to list all five properties of an algorithm. Know them by name and be able to give a one-line definition of each.
⚠️ Comparison and swap counts for best and worst cases of bubble sort and insertion sort are heavily tested. Memorise the formulas or be ready to derive them.
⚠️ Know when to use linear search vs binary search. If the array is unsorted, binary search is not an option.
⚠️ Exam questions may give you a specific array and ask you to trace through a sort step by step, counting comparisons and swaps.
True or false: Binary search has O(n) worst-case complexity. (False: it is O(log n).)
Fill in the blank: The best-case number of swaps for both bubble sort and insertion sort on an already-sorted array is ______. (0)
True or false: An algorithm that sometimes gives wrong answers still counts as an algorithm if it terminates. (False: correctness is a required property.)
Fill in the blank: Bubble sort's worst-case number of comparisons is ______. (n² - n)
True or false: Insertion sort builds a sorted section by repeatedly taking the first unsorted element and placing it correctly. (True.)
Q: List the five properties every algorithm must have.
A: Input, output, correctness, effectiveness, finiteness, and generality. (Some textbooks list five, folding effectiveness and finiteness together; this source lists all six distinctly.)
Q: An array contains [8, 5, 3, 1]. How many comparisons does bubble sort need in the first pass?
A: 3 comparisons (compare positions 1-2, 2-3, 3-4). Since the array is in reverse order, all three result in swaps.
Q: Why can you not use binary search on an unsorted array?
A: Binary search decides which half to discard based on whether the target is larger or smaller than the middle element. If the array is unsorted, that comparison gives no reliable information about which half contains the target.
Q: What is the best-case time complexity of insertion sort, and when does it occur?
A: O(n), with n - 1 comparisons and 0 swaps. This occurs when the array is already sorted, because each element is already in its correct position.
Q: In the worst case, how do bubble sort's comparison count and swap count compare?
A: Comparisons = n² - n. Swaps = (1/2)n² - (1/2)n. The comparison count is roughly double the swap count.
Search and sorting connect to growth functions (Big-O analysis is how you express their efficiency). Induction proofs are used to formally verify that these algorithms are correct. More advanced sorting algorithms (merge sort, quicksort) improve on the O(n²) bound you see here, and understanding why bubble sort and insertion sort are slow motivates the study of divide-and-conquer strategies.
algorithm properties, input, output, correctness, effectiveness, finiteness, generality, linear search, binary search, sequential search, sorted array, bubble sort, insertion sort, comparisons, swaps, best case, worst case, adjacent swap, non-decreasing order, O(n²), O(log n), O(n), sorting algorithms, search algorithms, CS 101, foundations of computer science