Difficulty: Foundational | Prerequisites: None (entry-level CS topic)
Tags: algorithm, pseudocode, linear search, binary search, bubble sort, selection sort, insertion sort, Big-O notation, asymptotic analysis, time complexity, space complexity, growth of functions, algorithm analysis, worst case, best case, CS182, discrete math, Purdue
This material forms the backbone of computational thinking. You are learning what an algorithm actually is (not just "code"), how to write pseudocode that communicates an algorithm clearly, how to search and sort data, and how to measure how fast an algorithm runs as input grows. If you cannot analyse an algorithm's complexity, you cannot compare two solutions or predict whether your code will finish in time. Everything in later CS courses (data structures, operating systems, AI) builds on these ideas.
An algorithm is a finite, precise sequence of steps that solves a problem. We analyse algorithms by counting dominant operations (usually comparisons or array accesses) and expressing runtime as a function of input size using Big-O notation. Big-O gives an upper bound on growth, letting us ignore constants and lower-order terms so we can compare algorithms fairly.
Algorithm
A finite sequence of precise instructions for performing a computation or solving a problem. It takes input from a specified set, produces output, and halts after finitely many steps. In simple terms, it is a recipe that always finishes and always gives you the right answer.
Pseudocode
An intermediate notation between plain English and actual programming code, used to describe algorithms without worrying about syntax details. Think of it as writing out your algorithm in structured English with keywords like for, if, while, and indentation to show structure.
Linear search
A searching method that compares the target element with each element in the array, one by one, from start to finish. In simple terms, you check every item until you find what you want or run out of items.
Binary search
A searching method for sorted arrays that repeatedly compares the target with the middle element, then discards half the remaining elements. Think of it as opening a dictionary to the middle, seeing whether your word comes before or after, and repeating on the correct half.
Big-O notation
A mathematical notation that describes an upper bound on the growth rate of a function. Formally, f(x) is O(g(x)) if there exist constants C and k such that |f(x)| <= C|g(x)| for all x > k. In simple terms, Big-O tells you the worst a function can grow, ignoring constant factors and small inputs.
Best case
The fastest possible runtime for an algorithm, which depends on getting a lucky input (e.g. the element you are searching for is the first one checked).
Worst case
The slowest possible runtime for an algorithm across all possible inputs of a given size. This is the standard guarantee because it does not depend on luck.
Time complexity
The amount of time (measured in operations) required to execute an algorithm as a function of input size.
Space complexity
The amount of memory required to execute an algorithm as a function of input size.
Every algorithm must satisfy these properties:
Input: values drawn from a specified set
Output: values produced for each set of inputs, representing the solution
Definiteness: each step must be precisely defined
Correctness: must produce the correct output for every valid input
Finiteness: must halt after a finite number of steps
Effectiveness: each step must be executable exactly, in finite time
Generality: must work for all problems of the desired form, not just one particular input
Define all variables and specify input/output
Use keywords (for, if else, while) and indentation to show structure
Simplify tedious procedures by describing them in words
Do not clutter with brackets or reference undefined variables
Do not write actual code when pseudocode is requested
Be consistent with notation within one algorithm
Example (finding the maximum in a sequence s₁, s₂, ..., sₙ):
procedure findMax(s, n)
myMax = s₁
i = 2
while i <= n do
if sᵢ > myMax then myMax = sᵢ endif
i = i + 1
endwhile
return(myMax)
end findMax
Given a collection of n elements and a target x, determine whether x is present and, if so, return its location.
Linear search: check each element sequentially. Works on unsorted arrays. Worst case: n comparisons, so O(n).
Binary search: requires a sorted array. Compare x with the middle element, then recurse on the appropriate half. Worst case: 1 + log₂ n comparisons, so O(log n).
Bubble sort: compare adjacent pairs and swap if out of order. Repeat passes until sorted. Best case: already sorted. Worst case: reverse-sorted array. Often called the easiest sorting algorithm to implement.
Selection sort: find the smallest unsorted element and place it in the next sorted position. Same runtime as bubble sort.
Insertion sort: take the current element and insert it into its correct position within the already-sorted portion of the array.
The goal is to express running time as a function of input size n, independent of machine speed, programming language, or coding style.
Choose a cost model: count the operation most likely to dominate runtime (comparisons, array accesses)
Counting every operation is tedious and unnecessary; focus on the dominant term
The worst case runtime provides a guarantee; the best case is input-dependent and less useful
Time to solve a problem depends on the number of operations (a function of input size) and the speed of hardware/software (a constant multiplier we can ignore).
Big-O strips away constant multipliers and lower-order terms
Assumes all basic operations take roughly the same time
Formal definition: f(x) is O(g(x)) if there exist constants C > 0 and k >= 0 such that |f(x)| <= C|g(x)| for all x > k
Big-O gives an upper bound, not necessarily a tight one. For example, log(n²) is O(log n), but it is also technically O(n) and O(n²). The tightest bound is what you should report.
To show f(n) is O(g(n)), choose specific values of C and k, then prove the inequality holds for all n > k.
Example: show 60n² + 5n + 1 is O(n²).
60n² + 5n + 1 <= 60n² + 5n + n² (since 1 <= n² for n >= 1)
<= 66n² (since 5n <= n² for n >= 5, but we can just bound 5n <= n² ... actually we bound each term by n²)
Choose C = 66, k = 1. Done.
To show f(n) is NOT O(g(n)), assume it is and derive a contradiction.
Example: show n² is not O(n).
Assume n² is O(n). Then there exist C, k such that n² <= Cn for all n > k.
This requires n <= C for all n > k, but no constant C is larger than all n. Contradiction.
Constant: O(1)
Logarithmic: O(log n)
Linear: O(n)
Linearithmic: O(n log n)
Quadratic: O(n²)
Cubic: O(n³)
Polynomial: O(nᵏ), k is a constant
Exponential: O(cⁿ), c is a constant > 1
Factorial: O(n!)
Complexity refers to both time and space required. When analysing complexity without the actual program, focus on the structural features that affect performance (loop counts, recursion depth).
Example cost model for a selection sort variant: count array accesses. A double loop over n elements yields O(n²) array accesses.
Recursive Fibonacci: each call for n > 1 makes two recursive calls, leading to O(2ⁿ) calls. Extremely slow for large n.
Dynamic Programming Fibonacci: store results in an array, iterate from 0 to n. Time: O(n). Space: O(n). Far more efficient because it avoids recomputing the same values.
A double for loop (i from 1 to n, j from 1 to n) with constant work inside: 2n² operations, which is O(n²).
A while loop where i doubles each iteration (i = 1, 2, 4, 8, ..., n): runs log₂ n times, so O(log n).
Logarithm Laws (base 2 assumed in CS unless stated otherwise):
Product rule: log(xy) = log x + log y
Quotient rule: log(x/y) = log x - log y
Power rule: log(xʸ) = y log x
Change of base: log_a(b) = log_c(b) / log_c(a)
log(1) = 0
Linear and binary search are used constantly in databases, search engines, and file systems. Understanding Big-O is how engineers decide whether a solution will scale: an O(n²) algorithm might work fine for 1,000 items but become unusable at 1,000,000. The Fibonacci example illustrates why dynamic programming is preferred in practice for problems with overlapping subproblems.
"Big-O gives the exact runtime." It does not. It gives an upper bound on the growth rate. Two O(n²) algorithms can have very different actual runtimes due to constant factors.
"Binary search works on any array." Binary search requires the array to be sorted. If the array is unsorted, use linear search.
"Best case analysis is useful for comparing algorithms." Best case is input-dependent and provides no guarantee. Always use worst case for meaningful comparisons.
"Big-O and tight bound are the same thing." Big-O is only an upper bound. Saying f(n) is O(n³) when f(n) is actually O(n) is technically correct but misleading. Always give the tightest bound you can find.
⚠️ Be able to write clean pseudocode with defined inputs, outputs, and variables. Exams test this directly.
⚠️ Know the formal definition of Big-O and be able to prove (or disprove) that f(n) is O(g(n)) by choosing C and k.
⚠️ Memorise the common growth functions in order. Exam questions frequently ask you to rank them.
⚠️ Understand why worst case is the standard measure, not best case.
⚠️ Simplify as much as possible on homework (noted explicitly in lecture 3.2).
⚠️ Be able to count operations in nested loops and determine Big-O from pseudocode.
True or False: Binary search has O(n) worst-case complexity.
Fill in the blank: Big-O notation gives an ______ bound on the growth of a function.
True or False: If f(n) is O(n²), then f(n) is also O(n³).
Fill in the blank: The worst case for linear search on n elements requires ______ comparisons.
True or False: A recursive Fibonacci implementation runs in O(n) time.
Answers: 1. False (it is O(log n)). 2. upper. 3. True. 4. n. 5. False (it is O(2ⁿ)).
Q: Prove that 3n² + 7n + 2 is O(n²).
A: For n >= 1, 7n <= 7n² and 2 <= 2n², so 3n² + 7n + 2 <= 3n² + 7n² + 2n² = 12n². Choose C = 12, k = 1.
Q: Why does binary search require a sorted array?
A: Binary search compares the target with the middle element and discards half the array based on whether the target is larger or smaller. This logic only works if the elements are in non-decreasing order.
Q: What is the worst-case number of comparisons for binary search on an array of 1,000 elements?
A: 1 + log₂(1000) ≈ 1 + 10 = 11 comparisons.
Q: Explain why a recursive Fibonacci implementation is O(2ⁿ) while a dynamic programming version is O(n).
A: The recursive version recomputes the same subproblems repeatedly, creating an exponentially branching call tree. The dynamic programming version stores each Fibonacci number once in an array and builds up from the base cases, doing constant work per element.
Q: A loop runs with i = 1, and each iteration doubles i (i = 2i) until i > n. How many iterations does it run?
A: The values of i are 1, 2, 4, 8, ..., so it runs log₂(n) times. The complexity is O(log n).
This material connects directly to number theory (Chapter 4), where you analyse algorithms like the Euclidean algorithm for GCD. It also connects to counting and probability (Chapters 6-7), where you need to count operations. In graphs (Chapter 10), you will analyse the complexity of graph traversal algorithms like BFS and DFS.
algorithm properties, pseudocode rules, searching algorithms, linear search, sequential search, binary search, half-interval search, bubble sort, selection sort, insertion sort, Big-O, Big Oh, asymptotic notation, upper bound, growth rate, time complexity, space complexity, worst case analysis, best case analysis, algorithm analysis, nested loop complexity, logarithm laws, log base 2, dynamic programming vs recursion, Fibonacci, common growth functions, CS 182, Purdue, discrete math algorithms