MGU Mathematics Series — Discrete Mathematics

Part IV: Graph Theory, Networks, and Algorithms

Algorithms · Pseudocode · Big-O · Complexity

Chapter 12 of 14

MGU Mathematics Series · Discrete Mathematics · Library Textbook Edition

Chapter 12:
Algorithms
and Complexity

Pseudocode, searching, sorting, correctness, operation counting, growth rates, and Big-O notation — the mathematics behind every computation

■ Not Calculus-Based ■

■ 14 Sections • Part IV of 5 ■

Builds on Chapters 5, 9, 10, and 11 · Prepares students for Chapter 13 and Computer Science

Chapter 12 — Front Matter

Purpose and Overview

This chapter introduces algorithms as the central objects of computer science and discrete mathematics. An algorithm is a precise, step-by-step procedure that solves a problem. But algorithms are not just procedures — they are mathematical objects that can be analyzed, compared, proved correct, and measured for efficiency. This chapter teaches you to read, write, trace, and evaluate algorithms. It also introduces complexity: the study of how the resource requirements of an algorithm grow as the size of the input grows.

By the end of this chapter, you will be able to write algorithms in pseudocode, trace algorithms on specific inputs, argue informally about correctness, count the operations an algorithm performs, describe growth rates, use Big-O notation to classify algorithms, and explain why efficiency matters when problems become large.

No calculus is required. The tools of this chapter are arithmetic, algebra, counting, sequences, tables, and careful reasoning.

Opening Question

Suppose you are looking for a specific name in a list of one million names. You could check each name one at a time from the beginning. That would work — eventually. But how long would it take? And is there a faster method? Now suppose someone told you the list is already sorted alphabetically. Could you use that structure to search faster? If so, how much faster? These questions are not just practical. They are mathematical. The study of algorithms asks: what steps solve this problem, and how many steps does it take? This chapter gives you the language and tools to answer those questions precisely.

Why This Chapter Matters

Every computation — every search, sort, calculation, encryption, database query, and network routing decision — is carried out by an algorithm. If you understand algorithms, you understand what computers actually do and why some computations are fast while others take impractically long.

Discrete mathematics provides the foundation for algorithmic reasoning. Counting arguments, induction, graph structures, modular arithmetic, logical conditions, and set operations all appear directly inside algorithm design and analysis. This chapter ties those earlier tools together by showing you how they operate inside the procedures that run on every computing device.

Algorithms also have limits. Some problems are so large that even the fastest algorithm cannot solve them in a practical amount of time. Understanding growth rates and complexity helps you see why those limits exist and what they mean for the design of real systems.

14Sections

12Objectives

23Key Terms

10+Worked Examples

Learning Objectives

1Define an algorithm and identify its essential properties.
2Describe what it means for an algorithm to have well-defined inputs, outputs, and steps.
3Read and write algorithms in structured pseudocode.
4Trace the execution of a linear search and a binary search on a given list.
5Trace the execution of a selection sort and an insertion sort on a given list.
6Explain what it means for an algorithm to be correct.
7Count the number of operations an algorithm performs for small inputs.
8Explain what a growth rate is and why it matters.
9Use Big-O notation to classify algorithms as constant, linear, quadratic, or exponential time.
10Compare polynomial and exponential growth and explain their significance.
11Describe how algorithmic efficiency affects the design of real systems.
12Identify common mistakes in algorithm writing and complexity reasoning.

Chapter 12 — Contents

Sections at a Glance

12.1What an Algorithm IsOrigins of the word; four essential properties: finite, precise, well-defined inputs and outputs; three guiding questions
12.2Inputs, Outputs, and StepsDomain and codomain; elementary operations; arithmetic, comparisons, assignments, control structures
12.3PseudocodeNotation conventions; assignments, comparisons, conditionals, loops, return statements; clarity over syntax
12.4Searching AlgorithmsLinear search; binary search; the role of sorted structure; worst-case comparisons
12.5Sorting Algorithms as an IntroductionSelection sort; insertion sort; tracing passes; behavior on different inputs
12.6Correctness of AlgorithmsTermination and partial correctness; loop invariants; informal correctness arguments
12.7Counting OperationsInput size; worst case; counting comparisons in linear search and selection sort
12.8Growth RatesComparing 2n, n², and 2ⁿ; feasibility versus infeasibility; dominant behavior
12.9Big-O NotationFormal definition; finding the Big-O class; dropping lower-order terms and constants
12.10Constant, Linear, Quadratic, and Exponential TimeComplexity classes O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ); examples and tables
12.11Polynomial Versus Exponential GrowthDefinitions; tractable versus intractable problems; n¹⁰⁰ versus 2ⁿ
12.12Algorithmic Efficiency in Real SystemsSearch engines, cryptography, databases, routing, AI/ML; merge sort; the Traveling Salesman Problem
12.13Common Algorithm and Complexity MistakesEight recurring errors; explanations and corrections
12.14Preparing for Computability and Data StructuresData structures; the Halting Problem; P vs. NP; bridge to Chapter 13

Section 12.1

What an Algorithm Is

The word "algorithm" comes from the name of the ninth-century Persian mathematician Muhammad ibn Musa al-Khwarizmi, whose work on systematic calculation procedures was enormously influential. Today, the word refers to any well-defined, step-by-step procedure for solving a problem.

An algorithm is not the same as a program. A program is an algorithm written in a specific programming language for a specific machine. An algorithm is the underlying idea — the sequence of logical steps — that could in principle be carried out by any suitable device, or even by hand.

Four Essential Properties of an Algorithm

Finite — An algorithm must eventually stop. A procedure that runs forever without producing an answer is not an algorithm. Every sequence of steps must be designed to reach a conclusion in a finite number of operations.

Precise — Every step of an algorithm must be unambiguous. There must be no room for guessing what the next action is. Vague instructions like "consider the elements" or "sort somehow" do not constitute algorithmic steps.

Well-defined input — An algorithm begins with specific data. The type and format of that data must be clearly specified.

Well-defined output — When an algorithm finishes, it must produce a clear result. Given the same input, the algorithm must always produce the same output.

Students sometimes confuse an algorithm with a rough description of a method. "Find the largest number in a list by looking through it" describes the idea of an algorithm, but it is not an algorithm until every step is spelled out in enough detail to be carried out mechanically, without interpretation or judgment.

Three Guiding Questions

The study of algorithms in discrete mathematics focuses on three questions. First: does this algorithm correctly solve the problem? Second: how many steps does it take? Third: how does the number of steps grow as the input grows larger?

MGU Library Connection

The MGU Computer Science pages cover algorithm implementation in programming languages
This chapter focuses on the mathematical analysis of algorithms, which underlies all programming
See the MGU Algorithms Reference for pseudocode style conventions and common algorithm families

Practice 12.1Concept Check

List the four essential properties of an algorithm. For each, give a short example of a "procedure" that fails to satisfy it.
Explain the difference between an algorithm and a program.
A friend says, "My algorithm checks if a number is even by figuring out whether it divides evenly by two." Is this description precise enough to be an algorithm? What would make it more precise?
Why is it useful to separate the question "is this algorithm correct?" from the question "how fast is this algorithm?"

Section 12.2

Inputs, Outputs, and Steps

Every algorithm has a domain — a description of the kinds of inputs it accepts — and a codomain — a description of the kinds of outputs it produces. Before writing an algorithm, you should be able to answer these questions precisely.

What form does the input take? Is it a single number, a list of numbers, a string of characters, a graph, a matrix, a Boolean value? What form does the output take? Is it a number, a sorted list, a yes-or-no answer, a path, a set of elements? What is the algorithm supposed to do with the input to produce the output?

The steps of an algorithm are elementary operations. These include arithmetic operations (addition, subtraction, multiplication, division), comparisons (is this value greater than that value?), assignments (store this value in that location), and control structures (repeat this step while this condition holds; if this condition is true, do this; otherwise, do that).

In theoretical algorithm analysis, we count each elementary operation as one step. In practice, the exact definition of "one step" depends on the context, but for the purposes of this chapter, we will count comparisons and assignments as basic units.

Worked Example 12.2.1

Identifying inputs and outputs

ProblemA student says: "My algorithm finds the maximum value in a list." Identify the input and output for this algorithm.
ThinkWe need to specify exactly what kind of object the input is and what kind of object the output is.
SolveThe input is a non-empty list of numbers. The output is a single number: the largest value in the list.
CheckIs the input well-defined? A list of numbers, yes. Is the output well-defined? The maximum value, yes. Is the specification complete? Not entirely — we should also specify what happens if the list is empty, since the maximum of an empty list is undefined. A complete algorithm would either exclude empty lists from its domain or specify how to handle them.

Answer: The input is a non-empty list of numbers. The output is the largest number in the list.

Practice 12.2Notation and Concept Practice

For an algorithm that takes two whole numbers and returns their greatest common divisor, identify the input and output precisely, including any restrictions.
For an algorithm that takes a list of names and returns the names in alphabetical order, identify the input and output.
For an algorithm that takes a graph and two vertices and returns whether a path exists between them, identify the input and output.
Classify each of the following as an arithmetic operation, a comparison, an assignment, or a control structure: x ← x + 1; if a > b; while count ≤ n; 5 × 3.

Section 12.3

Pseudocode

Pseudocode is the language we use to write algorithms clearly. It is not a real programming language, and it does not run on a computer. It is designed to be read by humans. Pseudocode must be precise enough to trace, but flexible enough to focus on logic rather than syntax.

Different textbooks and courses use different pseudocode conventions. In this textbook, we use the following conventions.

Convention	Meaning
`←`	Assignment. `max ← 0` means "set max equal to 0."
`< > ≤ ≥ = ≠`	Standard mathematical comparisons.
if / then / else / end if	Conditional execution of steps.
for / while / do / end	Loops that repeat a set of steps.
return	Produces the final output of the algorithm.
`// comment`	A note explaining what a step does. Does not affect execution.
Indentation	Shows which steps belong inside a conditional or loop.

Here is the structure of a typical pseudocode algorithm:

Algorithm Name(input parameters) // Description of what the algorithm does Step 1 Step 2 if (condition) then Step 3a else Step 3b end if for i from 1 to n do Step 4 end for return output

The goal of pseudocode is clarity. Every step should be clear enough that a careful reader could execute it by hand.

Worked Example 12.3.1

Writing an algorithm in pseudocode

ProblemWrite an algorithm that finds the maximum value in a non-empty list of \(n\) numbers.
ThinkWe want to find the largest element. A reasonable strategy is to begin by assuming the first element is the maximum, then check each remaining element and update the maximum whenever we find a larger one.
Algorithm MaxValue(list A of n numbers) // Returns the largest value in A max ← A[1] // Assume the first element is the maximum for i from 2 to n do if A[i] > max then max ← A[i] // Update max if a larger value is found end if end for return max
TraceSuppose the list is \([3, 7, 2, 9, 4]\).
• Set max ← 3.
• i = 2: A[2] = 7 > 3, so max ← 7.
• i = 3: A[3] = 2 < 7, no change.
• i = 4: A[4] = 9 > 7, so max ← 9.
• i = 5: A[5] = 4 < 9, no change.
• Return 9.
CheckThe maximum of \([3, 7, 2, 9, 4]\) is 9. Correct.

Answer: The algorithm correctly returns 9 after examining all five elements.

Student Warning

Do not confuse pseudocode with English prose. "Check each element" is English. "For \(i\) from 2 to \(n\) do: if \(A[i] > \text{max}\) then \(\text{max} \leftarrow A[i]\)" is pseudocode. Pseudocode has enough structure to be traced step by step. English prose does not.

Practice 12.3Pseudocode Practice

Write a pseudocode algorithm that, given a list of \(n\) numbers, finds the minimum value.
Write a pseudocode algorithm that, given a positive integer \(n\), computes \(n!\) (n factorial).
Identify the assignment statements, comparisons, and loop structure in the MaxValue algorithm above.
Rewrite the following English description as pseudocode: "Go through a list of test scores. Count how many are at least 90."

Section 12.4

Searching Algorithms

Searching is one of the fundamental problems in computing. Given a list of elements and a target value, determine whether the target appears in the list, and if so, where.

We study two searching algorithms: linear search and binary search. These two algorithms illustrate an important principle: the structure of the data — whether the list is sorted or unsorted — can dramatically change the efficiency of the search.

Linear Search

Linear search checks each element of the list one by one, starting from the beginning, until the target is found or the list is exhausted. It requires no special structure in the list — the elements can be in any order.

LinearSearch(list A of n elements, target t) // Returns the index of t in A, or "not found" if t is not in A for i from 1 to n do if A[i] = t then return i // Target found at position i end if end for return "not found"

Worked Example 12.4.1

Tracing a linear search

ProblemUse linear search to find the target value 7 in the list \([4, 2, 7, 1, 9]\).
ThinkBegin at the first element and compare each element to 7 in sequence.
Tracei = 1: A[1] = 4 ≠ 7.
i = 2: A[2] = 2 ≠ 7.
i = 3: A[3] = 7 = 7. Return index 3.
CheckThe value 7 is at position 3. Correct.

Answer: Linear search returns index 3. The target 7 was found after 3 comparisons.

Worked Example 12.4.2

Linear search with target not in list

ProblemUse linear search to find the target value 5 in the list \([4, 2, 7, 1, 9]\).
Tracei = 1: 4 ≠ 5.
i = 2: 2 ≠ 5.
i = 3: 7 ≠ 5.
i = 4: 1 ≠ 5.
i = 5: 9 ≠ 5.
End of list. Return "not found."

Answer: The value 5 is not in the list. Linear search required 5 comparisons — one for each element.

Binary Search

Binary search is a much more efficient algorithm for searching a sorted list. The key insight is that in a sorted list, you can eliminate half of the remaining elements with each comparison.

The idea: compare the target to the middle element of the current search region. If the target equals the middle element, you are done. If the target is smaller, search only the left half. If the target is larger, search only the right half. Repeat.

BinarySearch(sorted list A of n elements, target t) // Returns the index of t in A, or "not found" if t is not in A low ← 1 high ← n while low ≤ high do mid ← ⌊(low + high) / 2⌋ // Middle index (floor) if A[mid] = t then return mid else if A[mid] < t then low ← mid + 1 // Target is in the right half else high ← mid - 1 // Target is in the left half end if end while return "not found"

The notation \(\lfloor x \rfloor\) means the floor of \(x\) — the greatest integer less than or equal to \(x\). For example, \(\lfloor 3.5 \rfloor = 3\).

Worked Example 12.4.3

Tracing a binary search

ProblemUse binary search to find the target value 14 in the sorted list \([2, 5, 8, 11, 14, 17, 20]\).
ThinkThe list has 7 elements. Set low = 1, high = 7.
Trace Iteration 1: mid = ⌊(1+7)/2⌋ = 4. A[4] = 11. Since 11 < 14, set low ← 5.
Iteration 2: mid = ⌊(5+7)/2⌋ = 6. A[6] = 17. Since 17 > 14, set high ← 5.
Iteration 3: mid = ⌊(5+5)/2⌋ = 5. A[5] = 14 = 14. Return index 5.
CheckThe value 14 is at position 5. Correct. Binary search needed only 3 comparisons to find the target in a list of 7 elements.

Answer: Binary search returns index 5. The target 14 was found in 3 comparisons.

Student Tip

Binary search only works on sorted lists. Applying binary search to an unsorted list will produce incorrect results. Always verify that the list is sorted before using binary search.

Comparison: Linear Search Versus Binary Search

For a list of \(n\) elements: linear search examines up to \(n\) elements in the worst case, while binary search examines up to approximately \(\log_2 n\) elements in the worst case.

n (list size)	Linear search (worst case)	Binary search (worst case)
10	10	4
100	100	7
1,000	1,000	10
1,000,000	1,000,000	20
1,000,000,000	1,000,000,000	30

The difference is dramatic. For one billion elements, linear search may require one billion comparisons; binary search requires at most 30. This is the power of exploiting structure — and the reason that complexity analysis matters.

Practice 12.4Search Algorithm Tracing

Trace linear search on the list \([8, 3, 6, 1, 7, 4]\) with target \(t = 7\).
Trace linear search on the list \([8, 3, 6, 1, 7, 4]\) with target \(t = 5\).
Trace binary search on the sorted list \([1, 4, 7, 10, 13, 16, 19, 22]\) with target \(t = 10\).
Trace binary search on the sorted list \([1, 4, 7, 10, 13, 16, 19, 22]\) with target \(t = 6\).
Explain why binary search cannot be applied to the unsorted list \([8, 3, 6, 1, 7, 4]\) directly.

Section 12.5

Sorting Algorithms as an Introduction

Sorting is the problem of rearranging a list of elements into a specified order, typically ascending or descending. Searching, merging, displaying, and analyzing data often depends on having sorted data. Sorting algorithms are among the most studied procedures in computing.

We introduce two elementary sorting algorithms: selection sort and insertion sort. These algorithms are not the fastest sorting methods available, but they are clear and easy to analyze, which makes them ideal for learning.

Selection Sort

Selection sort works by repeatedly finding the smallest unsorted element and placing it at the front of the unsorted portion of the list.

SelectionSort(list A of n numbers) // Sorts A in ascending order for i from 1 to n - 1 do minIndex ← i // Assume position i holds the minimum for j from i + 1 to n do if A[j] < A[minIndex] then minIndex ← j // Update minimum position end if end for if minIndex ≠ i then swap A[i] and A[minIndex] // Place the minimum in position i end if end for

Worked Example 12.5.1

Tracing selection sort

ProblemSort the list \([5, 3, 8, 1, 4]\) using selection sort.
Trace Pass 1 (i = 1): Unsorted portion is \([5, 3, 8, 1, 4]\). Minimum is 1 at index 4. Swap A[1] and A[4]. List becomes \([1, 3, 8, 5, 4]\).
Pass 2 (i = 2): Unsorted portion is \([3, 8, 5, 4]\). Minimum is 3 at index 2. No swap needed. List stays \([1, 3, 8, 5, 4]\).
Pass 3 (i = 3): Unsorted portion is \([8, 5, 4]\). Minimum is 4 at index 5. Swap A[3] and A[5]. List becomes \([1, 3, 4, 5, 8]\).
Pass 4 (i = 4): Unsorted portion is \([5, 8]\). Minimum is 5 at index 4. No swap needed. List stays \([1, 3, 4, 5, 8]\).
CheckThe list \([1, 3, 4, 5, 8]\) is in ascending order. Correct.

Answer: Selection sort produces \([1, 3, 4, 5, 8]\) after 4 passes.

Insertion Sort

Insertion sort builds a sorted portion of the list one element at a time. It takes each new element from the unsorted portion and inserts it into the correct position in the sorted portion.

InsertionSort(list A of n numbers) // Sorts A in ascending order for i from 2 to n do key ← A[i] // Element to be inserted j ← i - 1 while j ≥ 1 and A[j] > key do A[j + 1] ← A[j] // Shift element right to make room j ← j - 1 end while A[j + 1] ← key // Insert key in correct position end for

Worked Example 12.5.2

Tracing insertion sort

ProblemSort the list \([5, 3, 8, 1, 4]\) using insertion sort.
Trace Pass 1 (i = 2): key = 3. Compare: A[1] = 5 > 3, shift 5 right. Insert 3 at position 1. List: \([3, 5, 8, 1, 4]\).
Pass 2 (i = 3): key = 8. Compare: A[2] = 5 < 8, stop. Insert 8 at position 3. No change. List: \([3, 5, 8, 1, 4]\).
Pass 3 (i = 4): key = 1. Compare: A[3] = 8 > 1, shift. A[2] = 5 > 1, shift. A[1] = 3 > 1, shift. Insert 1 at position 1. List: \([1, 3, 5, 8, 4]\).
Pass 4 (i = 5): key = 4. Compare: A[4] = 8 > 4, shift. A[3] = 5 > 4, shift. A[2] = 3 < 4, stop. Insert 4 at position 3. List: \([1, 3, 4, 5, 8]\).
CheckThe list \([1, 3, 4, 5, 8]\) is in ascending order. Correct.

Answer: Insertion sort produces \([1, 3, 4, 5, 8]\).

Student Tip

Both selection sort and insertion sort produce correct results, but they may perform very differently depending on the structure of the input. Insertion sort is fast on nearly sorted lists because few shifts are needed. Selection sort always performs the same number of comparisons regardless of the list's initial order.

Practice 12.5Sorting Algorithm Tracing

Trace selection sort on the list \([6, 2, 8, 3, 5]\). Show the list after each pass.
Trace insertion sort on the list \([6, 2, 8, 3, 5]\). Show the list after each pass.
Trace insertion sort on the already-sorted list \([1, 2, 3, 4, 5]\). How many comparisons are made?
Trace selection sort on the reversed list \([5, 4, 3, 2, 1]\). How many comparisons are made?

Section 12.6

Correctness of Algorithms

Writing an algorithm is not enough. We must also be confident that the algorithm produces the right answer for every valid input, not just for the examples we traced.

Definition — Correctness

An algorithm is correct if, for every valid input, it terminates and produces the correct output.

There are two components: Termination means the algorithm always stops after a finite number of steps. Partial correctness means that if the algorithm terminates, its output is correct.

Proving correctness formally requires techniques like loop invariants and structural induction. A loop invariant is a property that holds before the loop begins, remains true at the start of each iteration, and guarantees the desired result when the loop ends.

We will examine correctness arguments informally in this chapter and return to the formal idea when we discuss induction in Chapter 5 of the text.

Worked Example 12.6.1

Informal correctness argument for linear search

ClaimLinearSearch correctly finds the target \(t\) in list \(A\) if \(t\) is present, and returns "not found" otherwise.
ThinkWe reason informally about what the loop guarantees as it runs.
ProofThe loop checks every element of the list. If the target is present at some position \(k\), then when \(i = k\), the algorithm will find \(A[k] = t\) and return \(k\). If the target is not present, no comparison ever succeeds, and after checking all \(n\) elements, the algorithm returns "not found."
CheckBoth cases — target present and target absent — are handled, and the algorithm always halts after at most \(n\) iterations.

Conclusion: The algorithm is correct because it systematically checks every possibility and acts appropriately in both cases.

Worked Example 12.6.2

Why correctness arguments matter

ProblemA student writes the following algorithm to find the maximum value in a list. Is it correct? BrokenMax(list A of n numbers) max ← 0 for i from 1 to n do if A[i] > max then max ← A[i] end if end for return max
ThinkWhat happens if the list contains only negative numbers?
SolveSuppose \(A = [-3, -7, -1]\). The algorithm initializes max = 0, but 0 is not in the list. After the loop, max = 0, but the correct maximum is −1.
CheckThe algorithm fails on lists where all values are negative.

Conclusion: The algorithm is not correct. It produces the wrong answer for lists with all negative values. The fix is to initialize max with the first element of the list, as shown in Worked Example 12.3.1.

Common Mistake

Initializing a maximum-finding variable to 0 is a frequent error. Zero is not a safe initialization unless you are certain the list contains only non-negative values. Initialize with the first element of the list instead.

Practice 12.6Correctness Reasoning

Write an informal correctness argument for the MaxValue algorithm from Worked Example 12.3.1.
A student writes an algorithm to find the minimum value in a list, initializing min ← A[1] and then comparing with <. Trace through the logic and explain why this initialization is correct, unlike BrokenMax.
Identify an edge case (a special or unusual input) that should be considered when checking the correctness of LinearSearch. Does LinearSearch handle it correctly?
Explain in your own words the difference between termination and partial correctness. Give an example of an algorithm that terminates but is not partially correct.

Section 12.7

Counting Operations

To understand how efficient an algorithm is, we count the number of elementary operations it performs as a function of the input size \(n\).

The input size \(n\) typically represents the number of elements in a list, the number of digits in a number, the number of vertices in a graph, or whatever quantity best captures the scale of the problem.

We count comparisons and assignments as basic operations. We do not usually count the loop counter itself unless it is important to the analysis.

The worst case is the input that causes the algorithm to perform the most operations. We typically analyze worst-case behavior because it gives us a guaranteed upper bound.

Worked Example 12.7.1

Counting operations in linear search

ProblemHow many comparisons does linear search perform in the worst case on a list of \(n\) elements?
ThinkThe worst case occurs when the target is not in the list, or when it appears at the very last position. In either case, the algorithm compares the target to every element.
SolveThe loop runs from \(i = 1\) to \(i = n\). In each iteration, one comparison is made: \(A[i] = t\)? If the target is not found, all \(n\) comparisons are made.

Answer: Linear search performs at most \(n\) comparisons in the worst case.

Worked Example 12.7.2

Counting operations in selection sort

ProblemHow many comparisons does selection sort perform on a list of \(n\) elements?
ThinkSelection sort has two nested loops. The outer loop runs \(n - 1\) times. In pass \(i\), the inner loop makes \(n - i\) comparisons to find the minimum of the unsorted portion.
SolveCount the comparisons:
Pass 1: \(n-1\) comparisons.
Pass 2: \(n-2\) comparisons.
Pass 3: \(n-3\) comparisons.
…
Pass \(n-1\): 1 comparison.

Total comparisons: (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2
CheckFor \(n = 5\): \(\frac{5 \cdot 4}{2} = 10\). In our trace of Worked Example 12.5.1, let us verify: Pass 1 had 4 comparisons, Pass 2 had 3, Pass 3 had 2, Pass 4 had 1. Total: \(4 + 3 + 2 + 1 = 10\). Confirmed.

Answer: Selection sort performs \(\dfrac{n(n-1)}{2}\) comparisons in the worst case.

MGU Library Connection

The formula \(1 + 2 + 3 + \cdots + (n-1) = \dfrac{n(n-1)}{2}\) was proved using mathematical induction in Chapter 5
Algorithmic analysis frequently uses summation formulas from earlier chapters

Practice 12.7Operation Counting Practice

How many comparisons does linear search perform in the best case (the target is the first element)?
How many assignments to max occur in the worst case for the MaxValue algorithm on a list of \(n\) numbers that is sorted in increasing order?
An algorithm has one loop that runs from 1 to \(n\), and inside that loop, a second loop runs from 1 to \(n\) as well (not depending on the outer loop's counter). How many total iterations of the inner loop's body occur?
Use the formula from Worked Example 12.7.2 to find the number of comparisons selection sort performs for \(n = 10\) and for \(n = 100\).

Section 12.8

Growth Rates

The operation count of an algorithm is a function of the input size \(n\). When we compare algorithms, we care about how fast this function grows as \(n\) increases.

The growth rate of an algorithm's operation count tells us how dramatically the running time increases when the input gets larger.

Consider two algorithms: Algorithm A performs \(2n\) operations, and Algorithm B performs \(n^2\) operations. For small \(n\), both may seem acceptable. But as \(n\) grows, the difference becomes enormous.

n	2n	n²	2ⁿ
5	10	25	32
10	20	100	1,024
20	40	400	1,048,576
50	100	2,500	≈ 10¹⁵
100	200	10,000	≈ 10³⁰

Notice the third column: \(2^n\) grows so quickly that by \(n = 100\), it has already reached a number with 30 digits — far beyond what any practical computing system could handle.

Growth rates determine whether a problem is feasible or infeasible in practice. An algorithm with a small, slow-growing operation count will remain fast even for very large inputs. An algorithm with a large, fast-growing operation count becomes impractical quickly.

The key insight of complexity theory is that the growth rate — not the exact operation count — is what matters most. An algorithm that performs \(3n + 7\) operations and an algorithm that performs \(50n\) operations both grow linearly. They may differ by a constant factor, but they both scale in the same fundamental way. An algorithm that performs \(n^2\) operations, however, scales very differently.

Practice 12.8Growth Rate Practice

For \(n = 10\) and \(n = 20\), compute \(5n\), \(n^2\), and \(2^n\). By how much does each function increase when \(n\) doubles?
Two algorithms perform \(n + 100\) and \(10n\) operations, respectively. For small \(n\) (say \(n = 5\)), which performs fewer operations? For large \(n\) (say \(n = 1000\)), which performs fewer? Explain why this happens.
Explain in your own words why the growth rate of an algorithm matters more for large inputs than for small inputs.

Section 12.9

Big-O Notation

Big-O notation is a mathematical language for describing growth rates. It lets us say that an algorithm's operation count grows "no faster than" a certain function, ignoring constant factors and lower-order terms.

Definition — Big-O Notation

We say that \(f(n)\) is \(O(g(n))\) if there exist constants \(C > 0\) and \(N_0 \ge 1\) such that

f(n) ≤ C · g(n) for all n ≥ N₀.

In other words: beyond some input size \(N_0\), the function \(f(n)\) is always at most a constant multiple of \(g(n)\). The function \(g(n)\) is an upper bound on the growth of \(f(n)\).

For this chapter, we will work with Big-O intuitively rather than formally proving statements from the definition. The formal definition is provided here so you know what Big-O means precisely, but you will apply it mainly by identifying the dominant term in an operation count.

How to Find the Big-O Class of an Algorithm

Procedure

Step 1. Write the operation count as a polynomial or other algebraic expression in \(n\).

Step 2. Identify the fastest-growing term — the term that dominates when \(n\) is large.

Step 3. Drop all lower-order terms and constant coefficients.

Step 4. Write the result using Big-O notation.

Operation Count	Dominant Term	Big-O Class
`3n + 7`	`n`	`O(n)`
`n(n-1)/2 = n²/2 - n/2`	`n²`	`O(n²)`
`5`	no `n` term	`O(1)`
`4n³ + 2n² + n`	`n³`	`O(n³)`

Worked Example 12.9.1

Finding the Big-O class

ProblemAn algorithm performs \(6n^2 + 4n + 11\) operations. What is its Big-O class?
ThinkIdentify the dominant term. For large \(n\), \(6n^2\) dominates both \(4n\) and 11.
SolveThe dominant term is \(n^2\). Drop the coefficient 6. The result is \(O(n^2)\).
CheckFor \(n = 100\): \(6(10000) + 400 + 11 = 60{,}411\). The dominant term \(6n^2 = 60{,}000\) accounts for almost all of the total. The lower-order terms become relatively less significant as \(n\) grows.

Answer: The algorithm is \(O(n^2)\).

Worked Example 12.9.2

Big-O for selection sort

ProblemSelection sort performs \(\dfrac{n(n-1)}{2}\) comparisons. What is its Big-O class?
Solve\(\dfrac{n(n-1)}{2} = \dfrac{n^2 - n}{2} = \dfrac{n^2}{2} - \dfrac{n}{2}\). The dominant term is \(n^2\). Drop lower-order term and coefficient.

Answer: Selection sort is \(O(n^2)\).

Worked Example 12.9.3

Big-O for binary search

ProblemBinary search performs at most \(\lfloor \log_2 n \rfloor + 1\) comparisons. What is its Big-O class?
SolveThe dominant term is \(\log_2 n\). Drop the constant addend. Result: \(O(\log n)\).
CheckIn Big-O notation, we write \(O(\log n)\) without specifying the base, because logarithms in different bases differ only by a constant factor, and constant factors are absorbed into the Big-O.

Answer: Binary search is \(O(\log n)\).

Student Warning

Big-O notation captures growth rate, not exact operation count. \(O(n^2)\) does not mean exactly \(n^2\) operations. It means the operation count is bounded above by a constant multiple of \(n^2\) for large inputs. Two algorithms can both be \(O(n^2)\) but perform very different numbers of operations for small inputs.

Practice 12.9Big-O Classification Practice

An algorithm performs \(4n + 3\) operations. What is its Big-O class?
An algorithm performs \(2n^2 + 5n + 1\) operations. What is its Big-O class?
An algorithm performs \(7\) operations regardless of input size. What is its Big-O class?
An algorithm performs \(\dfrac{n(n+1)}{2}\) operations. What is its Big-O class?
An algorithm has two phases: the first phase takes \(O(n)\) time and the second takes \(O(n^2)\) time. What is the overall Big-O class? Explain your reasoning.

Section 12.10

Constant, Linear, Quadratic, and Exponential Time

Algorithms are classified into complexity classes based on their Big-O growth rate. The most common classes in introductory discrete mathematics are constant, logarithmic, linear, linearithmic, quadratic, and exponential.

Constant Time: O(1)

A constant-time algorithm performs the same number of operations regardless of the input size. The word "constant" does not mean one operation — it means the operation count does not depend on \(n\).

Example: Accessing the first element of a list. Whether the list has 5 elements or 5 million elements, retrieving the first element takes the same amount of work.

Logarithmic Time: O(log n)

A logarithmic-time algorithm's operation count grows proportionally to the logarithm of the input size. Doubling the input size adds only a constant number of additional operations.

Example: Binary search. If a list of 1,000 elements requires 10 comparisons, a list of 2,000 elements requires at most 11. Logarithmic algorithms are extremely efficient. They can handle enormous inputs with a manageable number of steps.

Linear Time: O(n)

A linear-time algorithm performs a number of operations proportional to the input size. Doubling the input roughly doubles the work.

Example: Linear search. Examining one million elements requires at most one million comparisons. Linear time is generally considered efficient for most practical applications.

Linearithmic Time: O(n log n)

A linearithmic algorithm performs slightly more work than linear but much less than quadratic. Many efficient sorting algorithms — including Merge Sort and Heap Sort — run in \(O(n \log n)\) time.

Quadratic Time: O(n²)

A quadratic-time algorithm's operation count grows proportionally to the square of the input size. Doubling the input roughly quadruples the work.

Example: Selection sort and insertion sort. For 1,000 elements, the work is proportional to 1,000,000 operations. For 10,000 elements, the work is proportional to 100,000,000 operations. Quadratic algorithms are acceptable for small inputs but become impractical for large ones.

Exponential Time: O(2ⁿ), O(3ⁿ), etc.

An exponential-time algorithm's operation count grows proportionally to a power of a fixed base raised to \(n\). Adding one element to the input can double or triple the required work.

Example: An algorithm that checks every possible subset of a set of \(n\) elements must examine \(2^n\) subsets. For \(n = 30\), that is more than one billion subsets. For \(n = 60\), it is more than one quintillion. Exponential algorithms are typically impractical for inputs larger than about 20 to 30, depending on the base and the speed of the computing hardware.

Big-O Class	Name	n = 10	n = 100	n = 1000
`O(1)`	Constant	1	1	1
`O(log n)`	Logarithmic	~3	~7	~10
`O(n)`	Linear	10	100	1,000
`O(n log n)`	Linearithmic	~33	~664	~9,966
`O(n²)`	Quadratic	100	10,000	1,000,000
`O(2ⁿ)`	Exponential	1,024	≈ 10³⁰	Astronomically large

Practice 12.10Complexity Class Practice

Classify each as one of the complexity classes from this section: (a) checking if a list of \(n\) numbers contains the value 0 by checking every element once; (b) comparing every pair of elements in a list of \(n\) numbers; (c) generating every subset of a set of \(n\) elements; (d) accessing the third element of an array.
Fill in a table showing \(\log_2 n\), \(n\), \(n \log_2 n\), \(n^2\), and \(2^n\) for \(n = 4, 8, 16, 32, 64\).
For each pair, determine which grows faster as \(n \to \infty\): (a) \(O(n)\) vs. \(O(n \log n)\); (b) \(O(n^2)\) vs. \(O(n \log n)\); (c) \(O(n^{10})\) vs. \(O(2^n)\).

Section 12.11

Polynomial Versus Exponential Growth

One of the most important distinctions in algorithm analysis is between polynomial and exponential growth.

Definitions

A polynomial algorithm has a Big-O class of \(O(n^k)\) for some fixed constant \(k\). Examples include \(O(n)\), \(O(n^2)\), \(O(n^3)\), and \(O(n^{10})\). Even \(O(n^{10})\) is polynomial.

An exponential algorithm has a Big-O class of \(O(c^n)\) for some constant \(c > 1\). Examples include \(O(2^n)\), \(O(3^n)\), and \(O(10^n)\).

The difference between polynomial and exponential growth is not a matter of degree — it is a matter of kind. No polynomial, however large its exponent, eventually falls behind every exponential.

To see why, compare \(n^{100}\) with \(2^n\). For small \(n\), \(n^{100}\) is much larger than \(2^n\). But as \(n\) grows, \(2^n\) will eventually overtake \(n^{100}\) and grow much faster — because \(n\) appears in the exponent of \(2^n\) but in the base of \(n^{100}\).

Problems that can be solved by polynomial algorithms are called tractable. In practice, this means they can be solved efficiently even for large inputs, at least in principle. Problems for which only exponential algorithms are known are called intractable — they cannot be solved in any practical sense for inputs beyond a small size.

Worked Example 12.11.1

Comparing polynomial and exponential growth

ProblemCompare the operation counts of a quadratic algorithm \((n^2)\) and an exponential algorithm \((2^n)\) as \(n\) increases.
Table n n^2 2^n 5 25 32 10 100 1,024 20 400 1,048,576 30 900 1,073,741,824 50 2,500 ~1.1 x 10^15
CheckFor small inputs, \(2^n\) and \(n^2\) are in the same rough order of magnitude. But by \(n = 30\), the exponential algorithm requires over one billion operations — far beyond what is practical — while the quadratic algorithm requires only 900.

Answer: Exponential growth overtakes polynomial growth rapidly and becomes impractical for even moderately large inputs.

Student Tip

A common misunderstanding is to think that a bigger exponent in a polynomial makes it "almost exponential." It does not. \(O(n^{100})\) is polynomial. It is slow for small inputs, but it grows fundamentally differently from \(O(2^n)\).

Practice 12.11Polynomial vs. Exponential Practice

Classify each of the following as polynomial or exponential: (a) \(O(n^5)\); (b) \(O(3^n)\); (c) \(O(n \log n)\); (d) \(O(2^n)\); (e) \(O(n^{100})\).
Explain in your own words why \(O(n^{100})\) is considered fundamentally different from \(O(2^n)\), even though \(n^{100}\) is larger than \(2^n\) for many values of \(n\).
A problem of size \(n = 20\) can be solved by an exponential algorithm in a reasonable amount of time. Explain why a problem of size \(n = 60\) using the same algorithm would not be reasonable, even though the size only tripled.

Section 12.12

Algorithmic Efficiency in Real Systems

The study of algorithmic complexity is not an abstraction. It has direct consequences for the design and feasibility of real computing systems.

Search engines must search billions of web pages in fractions of a second. The algorithms behind search engines use highly efficient data structures and search strategies — not linear search over billions of documents.

Cryptographic systems are designed so that encryption is efficient (polynomial time) but breaking the encryption without the key is infeasible (exponential time). The security of encryption protocols relies directly on the intractability of certain mathematical problems.

Database queries over large tables must return results quickly. Database designers use sorted indexes and efficient search strategies precisely to avoid linear-time scanning of every record.

Routing algorithms on networks must find efficient paths quickly. The Dijkstra algorithm introduced in Chapter 11 runs in \(O(n^2)\) time for a graph with \(n\) vertices using a simple implementation — which is efficient enough for most real networks.

Artificial intelligence and machine learning algorithms operate on datasets with thousands or millions of examples and features. Understanding whether a learning algorithm is \(O(n)\), \(O(n^2)\), or \(O(n^3)\) in its training time determines whether it is feasible at scale.

The core principle is simple: for small inputs, efficiency barely matters. For large inputs, it is the difference between possible and impossible.

Application: Sorting in Practice

Real systems use sorting algorithms that run in \(O(n \log n)\) time — faster than selection sort or insertion sort, which run in \(O(n^2)\). The algorithm known as Merge Sort achieves \(O(n \log n)\) by dividing the list in half, sorting each half recursively, and merging the sorted halves. This divide-and-conquer strategy is closely connected to the binary search approach and to the recurrence relations studied in Chapter 9.

Application: The Traveling Salesman Problem

The Traveling Salesman Problem asks: given a list of cities and the distances between them, what is the shortest route that visits every city exactly once and returns to the starting city?

This problem appears in logistics, manufacturing, and network design. Despite its simple statement, no polynomial-time algorithm for the general Traveling Salesman Problem is known. The best known exact algorithms are exponential in the number of cities. For 20 cities, that is manageable. For 200 cities, it is not.

This is an example of an NP-hard problem — a class of problems for which efficient algorithms may not exist. The study of such problems is part of theoretical computer science and complexity theory, which builds on the discrete mathematics developed throughout this book.

MGU Library Connection

The question of whether polynomial-time algorithms exist for NP-hard problems is one of the most famous unsolved problems in mathematics and computer science, known as the P vs. NP problem
See the MGU Theoretical Computer Science pages for more

Practice 12.12Applications

Password search. A cybersecurity system must search through a sorted database of 1,000,000 known compromised passwords to check if a given password appears. (a) How many comparisons does linear search require in the worst case? (b) How many comparisons does binary search require in the worst case? (Use \(\log_2(1{,}000{,}000) \approx 20\).) (c) Which algorithm would you choose for this system, and why?
Scheduling. A system must sort a list of 10,000 appointments by time. If selection sort requires \(\dfrac{n(n-1)}{2}\) comparisons, how many comparisons are needed for 10,000 appointments?
Encryption. An encryption system is secure because breaking it requires an algorithm that runs in \(O(2^{128})\) time. Suppose a computer can perform \(10^{18}\) operations per second. Approximately how many seconds would it take to run \(2^{128} \approx 3.4 \times 10^{38}\) operations?
Route planning. A GPS system uses Dijkstra's algorithm, which runs in \(O(n^2)\) time for a graph with \(n\) intersections. (a) If analyzing a city with 1,000 intersections takes 1 second, roughly how long would it take for a city with 10,000 intersections? (b) Why would an exponential-time routing algorithm be impractical?
Data analysis. A machine learning algorithm scans a dataset of \(n\) examples in \(O(n^2)\) time for training. The training dataset grows from 10,000 examples to 100,000 examples. By what factor does the training time roughly increase?

Section 12.13

Common Algorithm and Complexity Mistakes

Students learning algorithms and complexity for the first time frequently encounter the following difficulties.

Mistake 1 — Confusing Big-O with exact operation count

Big-O notation describes a growth rate, not an exact formula. Saying an algorithm is \(O(n^2)\) does not mean it performs exactly \(n^2\) operations. It means the operation count is bounded above by a constant multiple of \(n^2\) for large \(n\). An algorithm that performs \(3n^2 + 5n + 2\) operations is also \(O(n^2)\).

Mistake 2 — Thinking a smaller operation count always means a faster algorithm

For small inputs, an \(O(n^2)\) algorithm might actually be faster in practice than an \(O(n \log n)\) algorithm with large constants. Big-O describes behavior as \(n \to \infty\), not for every specific value of \(n\).

Mistake 3 — Applying binary search to an unsorted list

Binary search requires a sorted list. Applying it to an unsorted list produces incorrect results. Always sort first, or confirm that the list is sorted.

Mistake 4 — Conflating the base of a logarithm in Big-O

When we write \(O(\log n)\), the base of the logarithm does not matter, because logarithms in different bases differ only by a constant factor (a change of base). \(O(\log_2 n)\) and \(O(\log_{10} n)\) are the same Big-O class.

Mistake 5 — Treating exponential time as "just a little slower"

Students sometimes see \(2^{50}\) written as a large number and think it is inconvenient but manageable. \(2^{50} \approx 10^{15}\). Even if a computer performs \(10^{12}\) operations per second, this would take about 1,000 seconds. At \(2^{100}\), it becomes approximately \(10^{30}\) — trillions of years on the fastest hardware imaginable. Exponential growth is not just large; it becomes physically unreachable.

Mistake 6 — Forgetting to specify the worst case

When you say an algorithm "takes \(O(n)\) time," you should be clear about whether this refers to the worst case, best case, or average case. In this chapter, we analyze the worst case unless stated otherwise. Best-case analysis can be misleading: an algorithm that is fast when the input happens to be sorted may be slow when it is not.

Mistake 7 — Writing pseudocode that is too vague

Writing "find the minimum" as a single step is not pseudocode — it is description. Pseudocode must be precise enough to trace step by step. Every loop, condition, assignment, and return must be written explicitly.

Mistake 8 — Concluding that an algorithm is correct because it worked on one example

Tracing an algorithm on one or two inputs does not prove it is correct. Correctness requires that the algorithm works for every valid input. Thinking through edge cases — empty lists, single-element lists, lists where the target appears at the beginning or end, lists with repeated values — is part of thorough correctness analysis.

Practice 12.13Error Analysis

Problem 1

"I traced binary search on the list [7, 3, 1, 9, 4] and it returned the wrong answer. I think binary search has a bug."

What is the student's error?

Problem 2

"Selection sort is O(n²), so it performs exactly n² comparisons."

What is the error in this statement?

Problem 3

An algorithm performs 5n² + 3n + 2 operations. The student writes: "This is O(n) because 3n is one of the terms."

What is the error?

Problem 4

"An algorithm runs in O(n¹⁰⁰⁰) time. This is practically the same as exponential time."

What is the error in this reasoning?

Problem 5

"I tested my sorting algorithm on five lists, and it sorted them all correctly, so the algorithm is correct."

What is the error in this claim?

Section 12.14

Preparing for Computability and Data Structures

This chapter has introduced algorithms as mathematical objects and complexity as a way to classify their efficiency. The tools you now have — pseudocode, tracing, operation counting, Big-O notation — are the foundation for deeper study in computer science and theoretical mathematics.

Data structures are organized ways of storing data that support efficient algorithms. Arrays, linked lists, stacks, queues, trees, heaps, hash tables, and graphs are all data structures studied in computer science courses. The graph structures from Chapters 10 and 11 of this text are examples of data structures. Choosing the right data structure is inseparable from choosing the right algorithm.

Computability theory asks a more fundamental question: are there problems that no algorithm can solve, regardless of how much time it is given? The answer is yes. Alan Turing proved in 1936 that the Halting Problem — determining whether a given algorithm will eventually stop — cannot be solved by any algorithm. This result, and others like it, defines the boundary between what is computably possible and what is not.

The P vs. NP problem asks whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. This question connects complexity theory to cryptography, optimization, logic, and the foundations of mathematics. It remains unsolved.

The foundations for all of these topics are in discrete mathematics: logic, sets, functions, induction, graph theory, counting, and the algorithmic reasoning developed throughout this book.

Bridge Note

If you continue into computer science, you will study data structures, algorithm design (divide and conquer, dynamic programming, greedy algorithms), complexity classes, computability, and formal language theory. All of these fields draw directly from the discrete mathematics in this text. The tools of proof and precise reasoning from Chapters 4 and 5 are as essential as the algorithmic ideas in this chapter.

Practice 12.14Readiness Check

Name three data structures and briefly describe what kind of data each is good at storing or retrieving.
In your own words, explain what the Halting Problem asks, and why it might be surprising that no algorithm can solve it in general.
Explain why the P vs. NP problem matters to cryptography. (Hint: think about what it would mean if every NP problem also had a polynomial-time algorithm.)
Looking back at this chapter, list three discrete mathematics tools from earlier chapters that were used in analyzing algorithms here.

Chapter 12 — Back Matter

Chapter Summary

Sec 12.1An algorithm is a finite, precise, step-by-step procedure that accepts well-defined inputs and produces well-defined outputs. It is distinct from a program. The three guiding questions are: is it correct, how many steps does it take, and how does this grow with input size?
Sec 12.2Every algorithm has a domain (inputs) and codomain (outputs). Steps are elementary operations: arithmetic, comparisons, assignments, and control structures.
Sec 12.3Pseudocode is a structured, human-readable notation for writing algorithms. It uses assignments (←), conditionals (if/else), loops (for/while), and return statements.
Sec 12.4Linear search checks each element in sequence and runs in O(n) time. Binary search exploits a sorted list to search in O(log n) time, but requires the list to be sorted.
Sec 12.5Selection sort repeatedly selects the minimum of the unsorted portion. Insertion sort builds a sorted portion one element at a time. Both are O(n²) but behave differently on different inputs.
Sec 12.6An algorithm is correct if it terminates and produces the right output for every valid input. Correctness requires checking termination, partial correctness, and edge cases — not just example traces.
Sec 12.7The operation count of an algorithm is expressed as a function of input size n. The worst case gives an upper bound. Selection sort performs n(n-1)/2 comparisons; linear search performs at most n.
Sec 12.8The growth rate describes how an operation count scales as n increases. Growth rate, not exact count, determines whether an algorithm remains practical for large inputs.
Sec 12.9Big-O notation describes an upper bound on growth by identifying the dominant term and dropping constant factors and lower-order terms. f(n) is O(g(n)) if f(n) ≤ C·g(n) for large enough n.
Sec 12.10Common complexity classes are O(1), O(log n), O(n), O(n log n), O(n²), and O(2ⁿ). Each represents a fundamentally different rate of growth, illustrated by accessing an element, binary search, linear search, merge sort, selection sort, and subset enumeration.
Sec 12.11Polynomial algorithms are O(n^k) for fixed k and are generally tractable. Exponential algorithms are O(c^n) for c > 1 and become intractable rapidly. The distinction is a difference in kind, not degree.
Sec 12.12Algorithmic efficiency shapes search engines, cryptography, databases, routing, and machine learning. Merge sort achieves O(n log n) sorting; the Traveling Salesman Problem is an example of an NP-hard problem with no known polynomial-time solution.
Sec 12.13Eight recurring mistakes include confusing Big-O with exact counts, misapplying binary search to unsorted lists, underestimating exponential growth, and assuming correctness from limited testing.
Sec 12.14Data structures organize data to support efficient algorithms. The Halting Problem shows some problems are undecidable. The P vs. NP problem remains a central open question connecting complexity, cryptography, and logic.

Key Terms Review

algorithm

A finite, precise, step-by-step procedure that solves a problem or accomplishes a task.

input

The data provided to an algorithm before it begins.

output

The result produced by an algorithm when it finishes.

pseudocode

An informal, structured language used to describe algorithms in a form readable by humans and close to a programming language.

loop

A structure in an algorithm that repeats a set of steps.

conditional

A structure in an algorithm that executes steps only when a specified condition is true.

correctness

The property of an algorithm that guarantees it produces the right output for every valid input.

linear search

An algorithm that checks each element of a list one by one until the target is found or the list is exhausted.

binary search

An algorithm that searches a sorted list by repeatedly dividing the search region in half.

selection sort

A sorting algorithm that repeatedly selects the smallest remaining element and places it in its correct position.

insertion sort

A sorting algorithm that builds a sorted portion of the list one element at a time.

operation count

The number of elementary steps an algorithm performs, usually expressed as a function of input size.

input size

A measure of the amount of data given to an algorithm, typically denoted n.

growth rate

How an algorithm's operation count increases as the input size increases.

Big-O notation

A notation for describing an upper bound on the growth of a function, written O(f(n)).

constant time

An algorithm that always performs the same number of operations, regardless of input size: O(1).

logarithmic time

An algorithm whose operation count grows proportionally to the logarithm of the input size: O(log n).

linear time

An algorithm whose operation count grows in proportion to the input size: O(n).

quadratic time

An algorithm whose operation count grows proportionally to the square of the input size: O(n²).

exponential time

An algorithm whose operation count grows proportionally to a fixed base raised to the input size: O(2ⁿ), O(3ⁿ), etc.

polynomial algorithm

An algorithm whose operation count is bounded by a polynomial function of the input size, O(n^k).

tractable problem

A problem that can be solved in polynomial time for reasonably large inputs.

intractable problem

A problem for which no polynomial-time algorithm is known, making it impractical to solve for large inputs.

Concept Review Questions

What four properties must every algorithm satisfy?
What is pseudocode, and why is it useful for describing algorithms?
What is the difference between linear search and binary search? Under what conditions can binary search be used?
What does it mean to say that an algorithm is correct?
Why is the worst case the most common choice for analyzing an algorithm's operation count?
What does Big-O notation capture about an algorithm, and what does it deliberately ignore?
Why do we drop lower-order terms and constant coefficients when writing Big-O class?
What is the difference between polynomial growth and exponential growth? Why does this distinction matter in practice?
Describe one real-world situation in which the efficiency of an algorithm directly affects whether a system works or fails.
Why does binary search require a sorted list? What goes wrong if the list is not sorted?

Skill Practice

Part APseudocode Practice

Given a non-empty list of \(n\) numbers, write a pseudocode algorithm to find the minimum value.
Given a list of \(n\) numbers, write a pseudocode algorithm to count how many are even.
Given a list of \(n\) numbers, write a pseudocode algorithm to compute their sum.
Given a list of \(n\) numbers and a target \(t\), write a pseudocode algorithm to count how many times \(t\) appears in the list.
Given a list of \(n\) numbers, write a pseudocode algorithm to determine whether the list is sorted in ascending order. Return true if it is and false if it is not.

Part BAlgorithm Tracing

Trace linear search on the list \([8, 3, 6, 1, 7, 4]\) with target \(t = 7\).
Trace linear search on the list \([8, 3, 6, 1, 7, 4]\) with target \(t = 5\).
Trace binary search on the sorted list \([1, 4, 7, 10, 13, 16, 19, 22]\) with target \(t = 10\).
Trace binary search on the sorted list \([1, 4, 7, 10, 13, 16, 19, 22]\) with target \(t = 6\).
Trace selection sort on the list \([6, 2, 8, 3, 5]\).
Trace insertion sort on the list \([6, 2, 8, 3, 5]\).
Trace insertion sort on the already-sorted list \([1, 2, 3, 4, 5]\). How many comparisons are made?
Trace selection sort on the reversed list \([5, 4, 3, 2, 1]\). How many comparisons are made?

Part CRuntime Practice

An algorithm performs \(4n + 3\) operations. What is its Big-O class?
An algorithm performs \(2n^2 + 5n + 1\) operations. What is its Big-O class?
An algorithm performs \(\dfrac{n(n+1)}{2}\) operations. What is its Big-O class?
An algorithm performs \(7\) operations regardless of input size. What is its Big-O class?
An algorithm has two phases: the first phase takes \(O(n)\) time and the second takes \(O(n^2)\) time. What is the overall Big-O class?
Fill in the table below with the number of operations performed for each value of \(n\).

n	log₂ n	n	n log₂ n	n²	2ⁿ
4
8
16
32
64

Part DBig-O Classification

An algorithm that checks whether a list of \(n\) numbers contains the value 0 by checking every element once.
An algorithm that compares every pair of elements in a list of \(n\) numbers. How many pairs are there?
An algorithm that solves a problem by generating every subset of a set of \(n\) elements.
Linear search in the worst case.
Binary search in the worst case.
Selection sort in the worst case.
An algorithm that runs in 5 steps regardless of \(n\).
An algorithm with operation count \(3n^3 + 2n^2 + n + 100\).

Applications

For each problem, show your work and explain your reasoning in context.

Password search. A cybersecurity system must search through a sorted database of 1,000,000 known compromised passwords to check if a given password appears. (a) How many comparisons does linear search require in the worst case? (b) How many comparisons does binary search require in the worst case? (Use \(\log_2(1{,}000{,}000) \approx 20\).) (c) Which algorithm would you choose for this system, and why?
Scheduling. A system must sort a list of 10,000 appointments by time. If selection sort requires \(\dfrac{n(n-1)}{2}\) comparisons, how many comparisons are needed for 10,000 appointments?
Encryption. An encryption system is secure because breaking it requires an algorithm that runs in \(O(2^{128})\) time. Suppose a computer can perform \(10^{18}\) operations per second. Approximately how many seconds would it take to run \(2^{128} \approx 3.4 \times 10^{38}\) operations?
Route planning. A GPS system uses Dijkstra's algorithm, which runs in \(O(n^2)\) time for a graph with \(n\) intersections. (a) If analyzing a city with 1,000 intersections takes 1 second, roughly how long would it take for a city with 10,000 intersections? (b) Why would an exponential-time routing algorithm be impractical?
Data analysis. A machine learning algorithm scans a dataset of \(n\) examples in \(O(n^2)\) time for training. The training dataset grows from 10,000 examples to 100,000 examples. By what factor does the training time roughly increase?

Error Analysis

Each problem shows a student's claim or work. Identify the error and explain the correct reasoning.

Problem 1

"I traced binary search on the list [7, 3, 1, 9, 4] and it returned the wrong answer. I think binary search has a bug."

What is the student's error?

Problem 2

"Selection sort is O(n²), so it performs exactly n² comparisons."

What is the error in this statement?

Problem 3

An algorithm that performs 5n² + 3n + 2 operations. The student writes: "This is O(n) because 3n is one of the terms."

What is the error?

Problem 4

Student pseudocode for finding the maximum: BrokenMax(list A of n numbers) max ← 0 for i from 1 to n do if A[i] > max then max ← A[i] end if end for return max

Identify the error and explain when this algorithm produces a wrong answer.

Problem 5

"An algorithm runs in O(n¹⁰⁰⁰) time. This is practically the same as exponential time."

What is the error in this reasoning?

Problem 6

"I tested my sorting algorithm on five lists, and it sorted them all correctly, so the algorithm is correct."

What is the error in this claim?

Chapter 12 Checkpoint

Complete without assistance — assesses all key skills and concepts from Chapter 12

Part 1 — Concepts

State the four properties that every algorithm must have.
What is Big-O notation, and what two things does it ignore?
Explain the difference between polynomial and exponential growth rates. Give one example of each.

Part 2 — Pseudocode

Write a pseudocode algorithm that, given a list \(A\) of \(n\) positive integers, returns the sum of all even numbers in the list.
Write a pseudocode algorithm that determines whether a given positive integer \(n\) is prime. (Hint: Check divisibility by all integers from 2 up to \(\lfloor \sqrt{n} \rfloor\).)

Part 3 — Tracing

Trace linear search on the list \([12, 5, 9, 3, 17, 8]\) with target \(t = 3\). How many comparisons are made?
Trace binary search on the sorted list \([2, 6, 10, 14, 18, 22, 26, 30]\) with target \(t = 22\). How many comparisons are made?
Trace selection sort on the list \([4, 7, 1, 6, 3]\). Show the list after each pass.

Part 4 — Complexity

An algorithm performs \(8n^2 + 4n + 12\) operations. State its Big-O class and explain your reasoning.
Classify each of the following as polynomial or exponential: (a) \(O(n^5)\); (b) \(O(3^n)\); (c) \(O(n \log n)\); (d) \(O(2^n)\); (e) \(O(n^{100})\).
A quadratic algorithm takes 4 seconds to solve a problem of size \(n = 100\). Approximately how long would it take for a problem of size \(n = 200\)?

Part 5 — Application

A database of 500,000 sorted records must be searched repeatedly. A system designer is choosing between linear search and binary search. Using \(\log_2(500{,}000) \approx 19\), compare the worst-case number of comparisons for each algorithm and recommend the better choice.
An algorithm for a cryptographic application runs in \(O(2^n)\) time. Explain why increasing the key size from \(n = 64\) bits to \(n = 128\) bits provides enormously more security, even if the hardware doubles in speed every few years.

Looking Ahead

Chapter 13: Boolean Algebra, Circuits, and Digital Logic

Chapter 12 gave you the tools to write, trace, and analyze algorithms — the procedures that drive every computation. Chapter 13 moves one level deeper, to the logical and physical foundation those procedures run on. You will study Boolean variables, Boolean operations, logic gates, and circuits, and you will see how the truth tables from Chapter 2 become the AND, OR, and NOT gates etched into silicon. De Morgan's Laws will return as tools for simplifying circuits, and binary numbers will connect counting and arithmetic to the way computers physically represent data. Together, Chapters 12 and 13 show that an algorithm is not just an abstract idea — it is implemented, gate by gate, in real hardware.

MGU Library Connection

Algorithm Complexity Reference — Appendix N of this textbook
Pseudocode Style Guide — Appendix P of this textbook
Recurrence Relations Reference — Appendix K of this textbook, for the analysis of Merge Sort and divide-and-conquer algorithms
Discrete Mathematics, Chapter 5: Mathematical Induction and Recursion, for loop invariants and summation formulas
Discrete Mathematics, Chapter 11: Trees, Paths, and Network Optimization, for Dijkstra's Algorithm and graph-based routing
MGU Computer Science pages: data structures, algorithm implementation, and the P vs. NP problem
MGU Dictionary entries: algorithm, pseudocode, Big-O notation, polynomial time, exponential time

Chapter 12:Algorithmsand Complexity

Purpose and Overview

Why This Chapter Matters

Learning Objectives

Sections at a Glance

What an Algorithm Is

Inputs, Outputs, and Steps

Pseudocode

Searching Algorithms

Linear Search

Binary Search

Comparison: Linear Search Versus Binary Search

Sorting Algorithms as an Introduction

Selection Sort

Insertion Sort

Correctness of Algorithms

Counting Operations

Growth Rates

Big-O Notation

How to Find the Big-O Class of an Algorithm

Constant, Linear, Quadratic, and Exponential Time

Constant Time: O(1)

Logarithmic Time: O(log n)

Linear Time: O(n)

Linearithmic Time: O(n log n)

Quadratic Time: O(n²)

Exponential Time: O(2ⁿ), O(3ⁿ), etc.

Polynomial Versus Exponential Growth

Algorithmic Efficiency in Real Systems

Application: Sorting in Practice

Application: The Traveling Salesman Problem

Common Algorithm and Complexity Mistakes

Preparing for Computability and Data Structures

Chapter Summary

Key Terms Review

Concept Review Questions

Skill Practice

Applications

Error Analysis

Chapter 12 Checkpoint

Chapter 12:
Algorithms
and Complexity