Sets

Before moving on, let us see some concrete examples of sets. These examples illustrate not just the versatility of what sets can represent, but also illustrate various ways of defining sets.

We have only scratched the surface of the kinds of objects we can represent using sets. Later on in the course, we will enrich our set of examples by studying sets of computer programs, sequences of numbers, and graphs.

Functions

Functions can have more than one input. For sets \(A_1, A_2, \dots, A_k\) and \(B\), a \(k\)-ary function \(f: A_1 \times A_2 \times \dots \times A_k \TO B\) is a function that takes \(k\) arguments, where for each \(i\) between \(1\) and \(k\), the \(i\)-th argument of \(f\) must be an element of \(A_i\), and where \(f\) returns an element of \(B\). We have common English terms for small values of \(k\): unary, binary, and ternary functions take one, two, and three inputs, respectively. For example, the addition operator \(+ : \R \times \R \TO \R\) is a binary function that takes two real numbers and returns their sum. For readability, we usually write this function as \(x+y\) instead of \(+(x,y)\).

A predicate is a function whose codomain is {True, False}.In other courses, you may see True and False represented as the numbers \(1\) and \(0\), respectively. For example, we can define the predicate \(Odd: \N \TO \{\TRUE,\FALSE\}\) by mapping all even numbers to False, and all odd numbers to True. Given a predicate \(P\) and element \(x\) of its domain, we say that \(x\) satisfies \(P\) when \(P(x)\) is True.

Predicates and sets have a natural equivalence that we will sometimes make use of in this course. Given a predicate \(P: A \TO \{\TRUE,\FALSE\}\), we can define the set \(\{x \mid x \IN A \text{ and } P(x) = \TRUE\}\), i.e., the set of elements of \(A\) which satisfy \(P\). On the flip side, given a subset \(S \subseteq A\), we can define the predicate \(P: A \TO \{\TRUE, \FALSE\}\) by \(P(x) = \TRUE\) if \(x \IN S\), and \(P(x) = \FALSE\) if \(x \notin S\). For example, consider the predicate \(\mathit{Even} : \N \TO \{\TRUE, \FALSE\}\) that is \(\TRUE\) exactly when its argument is even. This predicate corresponds to the set of natural numbers \(\{0, 2, 4, \dotsc \}\).

Summation and product notation

When performing calculations, we’ll often end up writing sums of terms, where each term follows a pattern. For example: \[\frac{1 + 1^2}{3 + 1} + \frac{2 + 2^2}{3 + 2} + \frac{3 + 3^2}{3 + 3} + \cdots + \frac{100 + 100^2}{3 + 100}\]

We will often use summation notation to express such sums concisely. We could rewrite the previous example simply as: \[\sum_{i=1}^{100} \frac{i + i^2}{3 + i}.\]

In this example, \(i\) is called the index of summation, and \(1\) and \(100\) are the lower and upper bounds of the summation, respectively. A bit more generally, for any pair of integers \(j\) and \(k\), and any function \(f : \Z \to \R\), we can use summation notation in the following way: \[\sum_{i=j}^k f(i) = f(j) + f(j+1) + f(j+2) + \dots + f(k).\]

We can similarly use product notation to abbreviate multiplication:Fun fact: the Greek letter \(\Sigma\) (sigma) corresponds to the first letter of “sum,” and the Greek letter \(\Pi\) (pi) corresponds to the first letter of “product.” \[\prod_{i=j}^k f(i) = f(j) \times f(j+1) \times f(j+2) \times \dots \times f(k).\]

It is sometimes useful (e.g., in certain formulas) to allow a summation or product’s lower bound to be greater than its upper bound. In this case, we say the summation or product is empty, and define their values as follows:These particular values are chosen so that adding an empty summation and multiplying by an empty product do not change the value of an expression.

• When \(j > k\), \(\sum_{i=j}^k f(i) = 0\).
• When \(j > k\), \(\prod_{i=j}^k f(i) = 1\).

Inequalities

Finally, in this course we will deal heavily with the manipulation of inequalities. While many of these operations are very similar to manipulating equalities, there are enough differences to warrant a comprehensive list.

The previous theorem tells us that basic operations like adding a number or multiplying by a positive number preserves inequalities. However, other operations like multiplying by a negative number or taking reciprocals reverses the direction of the inequality, which is something we didn’t have to worry about when dealing with equalities. But it turns out that, at least for non-negative numbers, most of our familiar functions preserve inequalities.

It should be clear from this definition that the following property holds, which enables us to manipulate inequalities using a host of common functions.

Propositional logic

We are now ready to begin our study of the formal language of logic. We will start with propositional logic, an elementary system of logic that is a crucial building block underlying other, more expressive systems of logic that we will need in this course.

In the following sections, we describe the various operators we will use in this course. It is important to keep in mind when reading that these operators inform both the structure of formulas (what they look like) as well as the truth value of these formulas (what they mean: whether the formula is \(\TRUE\) or \(\FALSE\) based on the truth values of the individual propositional variables).

Predicate logic

While propositional logic is a good starting point, most interesting statements in mathematics contain variables over domains larger than simply \(\{\TRUE, \FALSE\}\). For example, the statement “\(x\) is a power of 2” is not a proposition because its truth value depends on the value of \(x\). It is only after we substitute a value for \(x\) that we may determine whether the resulting statement is True or False. For example, if \(x = 8\), then the statement becomes “8 is a power of 2”, which is True. But if \(x = 7\), then the statement becomes “7 is a power of 2”, which is False.

A statement whose truth value depends on one or more variables from any set is a predicate: a function whose codomain is \(\{\TRUE, \FALSE\}\). We typically use uppercase letters starting from \(P\) to represent predicates, differentiating them from propositional variables. For example, if \(P(x)\) is defined to be the statement “\(x\) is a power of \(2\)”, then \(P(8)\) is True and \(P(7)\) is False. Thus a predicate is like a proposition except that it contains one or more variables; when we substitute particular values for the variables, we obtain a proposition.

As with all functions, predicates can depend on more than one variable. For example, if we define the predicate \(Q(x,y)\) to mean “\(x^2 = y\),” then \(Q(5,25)\) is True since \(5^2 = 25\), but \(Q(5,24)\) is False.Just as how common arithmetic operators like \(+\) are really binary functions, the common comparison operators like \(=\) and \(<\) are binary predicates, taking two numbers and returning True or False.

We usually define a predicate by giving the statement that involves the variables, e.g., “\(P(x)\) is the statement ‘\(x\) is a power of 2.’” However, there is another component which is crucial to the definition of a predicate: the domain that each of the predicate’s variable(s) belong to. You must always give the domain of a predicate as part of its definition. So we would complete the definition of \(P(x)\) as follows:

\[P(x): \text{``$x$ is a power of 2,'' \qquad where $x \IN \N$.}\]

Writing sentences in predicate logic

Now that we have introduced the existential and universal quantifiers, we have a complete set of tools needed to represent all statements we’ll see in this course. A general formula in predicate logic is built up using the existential and universal quantifiers, the propositional operators \(\NOT\), \(\AND\), \(\OR\), \(\IMP\), and \(\IFF\), and arbitrary predicates. To ensure that the formula has a fixed truth value, we will require every variable in the formula to be quantified.Other texts will often refer to quantified variables as bound variables, and unquantified variables as free variables. We call a formula with no unquantified variables a sentence. So for example, the formula \[\forall x \in \N,~ x^2 > y\] is not a sentence: even though \(x\) is quantified, \(y\) is not, and so we cannot determine the truth value of this formula. If we quantify \(y\) as well, we get a sentence: \[\forall x, y \in \N,~ x^2 > y.\]

However, don’t confuse a formula being a sentence with a formula being True! As we’ll see repeatedly throughout the course, it is quite possible to express both True and False sentences, and part of our job will be to determine whether a given sentence is True or False, and to prove it.

Defining predicates

Throughout this course, we will study various mathematical objects that play key roles in computer science. As these objects become more complex, so too will our statements about them, to the point where if we try to write out everything using just basic set and arithmetic operations, our formulas won’t fit on a single line! To avoid this problem, we create definitions, which we can use to express a long idea using a single term.This is completely analogous to using local variables or helper functions in programming to express part of an overall value or computation.

In this section, we’ll look at one extended example of defining our own predicates and using them in our statements. Let’s take some terminology that is already familiar to us, and make it precise using the language of predicate logic.

As you can see, using this new predicate makes our formula quite a bit more concise! But the usefulness of our definitions doesn’t stop here: we can, of course, use our terms and predicates in further definitions.

Our conventions for writing formulas

Mathematical expressions in predicate logic can become complicated very quickly. In order to avoid confusion and to make things as clear as possible we will follow some important conventions.

Some basic examples

We’re going to start out our exploration of proofs by studying a few simple statements. You may find our first few examples a bit on the easy side, which is fine. We are using them not so much for their ability to generate mathematical insight, but rather to model both the thinking and the writing that would go into approaching a problem.

Each example in this chapter is divided into three or four parts:

1. The statement that we want to prove or disprove. Sometimes, we’ll specify whether to prove or disprove it, and other times deciding whether the statement is true or false is part of the exercise.
2. A translation of the statement into predicate logic. This step often provides insight into the logical structure of the statement that we are considering, which in turn informs the structure and techniques that we will use in our proofs.
3. A discussion to try to gain some intuition about why the statement is true. You’ll tend to see that these are written very informally, as if we are talking to a friend on a whiteboard. The discussion usually will reveal the mathematical insight that forms the content of a proof. This is often the hardest part of developing a proof, so please don’t skip these sections!
4. A formal proof. This is meant to be a standalone piece of writing, the “final product” of our earlier work. Depending on the depth of the discussion, the formal proof might end up being almost mechanical – a matter of formalizing our intuition.

With this in mind, let’s dive right in!

That was perhaps an underwhelming proof, and rightfully so: statements that do not contain any variables are generally very straightforward to prove or disprove, because they usually amount to performing just some kind of calculation. However, almost all of the statements we care about involve quantified variables, and so we will next discuss how to deal with these quantifications so that the core of our proofs become “just a calculation.”

We can draw from this example a more general technique for structuring our existence proofs. A statement of the form \(\exists x \in S,~P(x)\) is True when at least one element of \(S\) satisfies \(P\). The easiest way to convince someone that this is True is to actually find the concrete element that satisfies \(P\), and then show that it does.Of course, this is not the only proof technique used for existence proofs. You’ll study more sophisticated ways of doing such proofs in future courses. This is so natural a strategy that it should not be surprising that there is a “standard proof format” when dealing with such statements.

Note that the two blanks represent the same element of \(S\), which you get to choose as a prover. Thus existence proofs usually come down to finding a correct element of the domain which satisfy the required properties.

The above proof has a few interesting details. The first is that this was a proof of a universally-quantified statement. Unlike the previous example, where we proved a fact about just one number, here we proved a fact about an infinite set of numbers.

To do this, our proof introduced a variable \(n\) that could represent any real number. Unlike the previous existence proof, when we introduced this variable \(n\) we did not specify a concrete value like \(10\), but rather said that \(n\) was “an arbitrary real number,” and then proceeded with the proof. As we get more comfortable, we will drop the English phrase part and just write “let \(n \in S\)” to introduce \(n\) as an arbitrary element of \(S\).You might notice that we use the same word “let” to introduce both existentially- and universally-quantified variables. However, you should always be able to tell how the variable is quantified based on whether it is given a concrete value or an “arbitrary” value in the proof.

However, this structure does not tell the full story. We also put a further restriction on \(n\): “Assume that \(n > 20\).” Whenever we want to prove that an implication \(p \IMP q\) is true, we do so by assuming that \(p\) is true, and then proving that \(q\) must be true.

Of course, these proof templates can be combined as the statements you prove grow more complex. In particular, statements of the form \(\forall n \in S,~P(n) \IMP Q(n)\) are probably the most common type of statements you’ll prove, and follow the standard setup of “Let \(n \in S\) be an arbitrary element of \(S\), and assume \(P(n)\) is True.”Compare this with the first line of the previous proof.

What goes into a proof?

We have now seen our first few basic examples of formal mathematical proofs. In the next section, we will create more complex proofs by studying some definitions and properties based in number theory. But to ensure that we have a solid foundation before moving on, we will first take a step back and give names to two major components of every proof and guidelines for writing them, based on the examples we have already seen.

A new domain: number theory

One of the biggest questions that arises from the idea of “proof as communication” is determining how much detail to go into. For this course, we are assuming only basic knowledge of arithmetic, algebraic manipulations of equalities and inequalities, and standard elementary functions like powers, logarithms, and trigonometric functions, but no calculus.So you may use, without justifications, various laws like \(a^b \cdot a^c = a^{b+c}\) and \(\sin^2 \theta + \cos^2 \theta = 1\). However, there is even variation in the typical CSC165 student with experience in this area, so as much as possible in this course, we will introduce new mathematical domains to serve as the objects of study in our proofs.

This approach has three very nice benefits: first, by building domains from the ground up, we can specify absolutely the common definitions and properties that everyone may assume and use freely in proofs; second, these domains are the theoretical foundation of many areas of computer science, and learning about them here will serve you well in many future courses; and third, learning about new domains will help develop the skill of reading about a new mathematical context and understanding it.In other words, you won’t just learn about new domains; you’ll learn how to learn about new domains! The definitions and axioms of a new domain communicate the foundation upon which we build new proofs – in order to prove things, we need to understand the objects that we’re talking about first.

Our first foray into domain exploration will be into number theory, which you can think of as taking a type of entity with which we are quite familiar, and formalizing definitions and pushing the boundaries of what we actually know about these numbers that we use every day. We’ll start off by repeating and expanding on one definition from the previous chapter.

Divisibility is a nice definition to work with because it contains an existential quantifier embedded in the definition. From this, we’ll see some proofs with more complex structure, based on the greater complexity of the statement.

The previous example is the first one that had multiple quantifiers. In our proof, we had to give explicit values for both \(a\) and \(k\) to show that the statement held. Just as how a sentence in predicate logic must have all its variables quantified, a mathematical proof must introduce all variables contained in the sentence being proven.

Alternating quantifiers revisited

In the previous chapter, we saw how changing the order of an existential and universal quantifier changed the meaning of a statement. Now, we’ll study how the order of quantifiers changes how we can introduce variables in a proof.

In this proof, we used an extremely important tool at our disposal when it comes to proofs with multiple quantifiers: any existentially-quantified variable can be assigned a value that depends on the variables defined before it.

In our proof, we first defined \(n\) to be an arbitrary integer. Immediately after this, we wanted to show that for this \(n\), \(\exists k \in \N, n = 1 \cdot k\). And to prove this, we needed a value for \(k\)—a “let” statement. Because we define \(k\) after having defined \(n\), we can use \(n\) in the definition of \(k\) and say “Let \(k = n\).” It may be helpful to think about the analogous process in programming. We first initialize a variable \(n\), and then define a new variable \(k\) that is assigned the value of \(n\).

Even though this may seem obvious, one important thing to note is that the order of variables in the statement determines the order in which the variables must be introduced in the proof, and hence which variables can depend on which other variables. For example, consider the following erroneous “proof.”

This proof may look very similar to the previous one, but it contains one crucial difference. The very first sentence, “Let \(k = n\),” is invalid: at that point, \(n\) has not yet been defined! This is the result of having switched around the order of the quantifiers, which forces \(k\) to be defined independently of whatever \(n\) is chosen.

Note: don’t assume that just because one proof is invalid, that all proofs of this statement are invalid! We cannot conclude that this statement is false just because we found one proof that didn’t work.A meta way of looking at this: a statement is true if there exists a correct proof of it. We’ll next look at how to prove that this statement is indeed false.

False statements and disproofs

Suppose we have a friend who is trying to convince us that a certain statement \(X\) is false. If they tell you that statement \(X\) is false because they tried really hard to come up with a proof of it and failed, you might believe them, or you might wonder if maybe they just missed a crucial idea leading to a correct proof.Maybe they skipped all their CSC165 classes. An absence of proof is not enough to convince us that the statement is false.

Instead, we must see a disproof, which is simply a proof that the negation of the statement is true.In other words, if we can prove that \(\NOT X\) is true, then \(X\) must be false. For this section, we’ll be using the simplification rules from the first chapter to make negations of statements easier to work with.

Here are two examples: the first one is quite simple, and is used to introduce the basic idea. The second is more subtle, and really requires good understanding of how we manipulate a statement to get a simple form for its negation.

When we want disprove a universally-quantified statement (“every element of \(S\) satisfies predicate \(P\)”), the negation of that statement becomes an existentially-quantified one (“there exists an element of \(S\) that doesn’t satisfy predicate \(P\)”). Since proofs of existential quantification involve just finding one value, the disproof of the original statement involves finding such a value which causes the predicate to be false (or alternatively, causes the negation of the predicate to be true). We call this value a counterexample for the original statement. In the previous example, we would say that 7 is a counterexample of the given statement.

Now let’s look at at a more complex disproof.

Proof by cases

The previous proof illustrated a new proof technique known as proof by cases. Remember that for a universal proof, we typically let a variable be an arbitrary element of the domain, and then make an argument in the proof body to prove our goal statement. However, even when the goal statement is true for all elements of the domain, it isn’t always easy to construct a single argument that works for all of those elements! Sometimes, different arguments are required for different elements. In this case, we divide the domain into different parts, and then write a separate argument for each part.

A bit more formally, we pick a set of unary predicates \(P_1\), \(P_2\), …, \(P_k\) (for some positive integer \(k\)), such that for every element \(x\) in the domain, \(x\) satisfies at least one of the predicates (we say that these predicates are exhaustive). You should think of these predicates as describing how we divide up the domain; in the previous example, the predicates were: \[P_1(c): c \leq 2, \qquad P_2(c): c \geq 4, \qquad P_3(c): c = 3.\]

Then, we divide the proof body into cases, where in each case we assume that one of the predicates is True, and use that assumption to construct a proof that specifically works under that assumption. Recall that there’s an equivalence between predicates and sets. Another way of looking at a proof by cases is that we divide the domain into subsets \(S_1, S_2, \dots S_k\), and then prove the desired statement separately for each of these subsets.

Proof by cases is a very versatile proof technique, since it allows the combining of simpler proofs together to form a whole proof. Often it is easier to prove a property about some (or even most) elements of the domain than it is to prove that same property about all the elements. But do keep in mind that if you can find a simple proof which works for all elements of the domain, that’s generally preferable than combining multiple proofs together in a proof by cases.

To see one natural use of proof by cases in number theory, we introduce the following theorem, which formalizes our intuitions about another familiar term: remainders.

The reason this theorem is powerful is that it tells us that for any divisor \(d \in \Z^+\), we can separate all possible integers into \(d\) different groups, corresponding to their possible remainders (between \(0\) and \(d-1\)) when divided by \(d\). Let’s see this how to use this fact to perform a proof by cases.

Generalizing statements

In this section, we will investigate another important skill for reading and writing proofs: the ability to generalize existing knowledge into more generic, and powerful, forms. As usual, we start with an example.

Proof by contrapositive

Let us now look at one example that is very similar to the previous one.

When proving an implication, it is often the case that the assuming the hypothesis does not get you very far. Flipping the implication around to its contrapositive and assuming the negation of the conclusion might yield better results!

Characterizations

We will now look at a pair of related examples that both demonstrate how to prove a biconditional, and illustrate one of the common goals of mathematical study: finding alternative useful characterizations of definitions. In particular, we’ll show that prime numbers are exactly the numbers greater than \(1\) that satisfy the following predicate: \[Atomic(n):~~ \forall a,b \in \N,~ n \NDIV a \AND n \NDIV b \IMP n \NDIV ab, \qquad \text{where $n \in \N$}\]

What we have just proven is that if \(n\) is greater than \(1\) and satisfies the \(Atomic\) predicate, then it must be prime. This rules out the possibility that \(n = 6\) satisfies this property, for example. But what about \(n = 5\)? This statement doesn’t actually tell us that \(5\) satisfies this property! So next, we’ll prove the converse of the implication.

Greatest common divisor

Let us now introduce one more definition that you’re probably familiar with, though again we will take some time to treat it more formally than what you may have seen before.

To make it easier to translate this statement into symbolic form, we can restate the “maximum” part by saying that if \(e\) is any number which divides \(m\) and \(n\), then \(e \leq d\). Let \(m, n, k \in \N\), not all of which are \(0\), and suppose \(k = \gcd(m, n)\). Then \(k\) satisfies the following statement: \[k \DIV m \AND k \DIV n \AND \big(\forall e \in \N,~e \DIV m \AND e \DIV n \IMP e \leq k \big).\]

You might wonder whether this definition makes sense in all cases: is it possible for two numbers to have no divisors in common? But remember that one of the statements we proved in this chapter is that \(1\) divides every natural number. So at the very least, \(1\) is a common divisor between any two natural numbers.

Here is an example which makes use of both this definition, and the definition of prime from the previous chapter.

Next, we will look at one of the strongest properties of the greatest common divisor: it is the smallest natural number that can be written as a sum of (positive or negative) multiples of the two numbers.

We will not prove this theorem here; instead, our main goal for stating it is to introduce a new proof technique: using an external statement as a step in a proof. This might sound kind of funny—after all, many of our proofs so far have relied on some algebraic manipulations which are valid but are really knowledge we learned prior to this course. The subtle difference is that those algebraic laws we take for granted as “obvious” because we learned them so long ago. But in fact our proofs can consist of steps which are statements that we know are true because of an external source, even one that we don’t know how to prove ourselves.

This is a fundamental parallel between writing proofs and writing computer programs. In programming, we start with some basic building blocks of a language—data types, control flow constructs, etc.—but we often rely on libraries as well to simplify our tasks. We can use these libraries by reading their documentation and understanding how to use them, but don’t need to understand how they are implemented. In the same way, we can use an external theorem in our proof by understanding what it means, but without knowing how to prove it.

Modular arithmetic

The final definition in this chapter introduces some notation that is extremely commonplace in number theory, and by extension in many areas of computer science. Often when we are dealing with relationships between numbers, divisibility is too coarse a relationship: as a predicate, it is constrained by the binary nature of its output. Instead, we often care about the remainder when we divide a number by another.

This definition captures the idea that \(a\) and \(b\) have the same remainder when divided by \(n\). You should think of this congruence relation as being analogous to numeric equality, with a relaxation. When we write \(a = b\), we mean that the numeric values of \(a\) and \(b\) are literally equal. When we write \(a \equiv b \MOD n\), we we mean that if you look at the remainders of \(a\) and \(b\) when divided by \(n\), those remainders are literally equal.

We will next look at how addition, subtraction, and multiplication all behave in an analogous fashion under modular arithmetic. The following proof is a little tedious because it is calculation-heavy; the main benefits here are practicing reading and using a new definition, and getting comfortable with this particular notation.

You may be wondering why we left out division in the above theorem. Recall again the definition of divisibility: \(a \DIV b\) means that there exists \(k \in \N\) such that \(b = ka\). Not every pair of integers is related by divisibility, and this also transfers over to modular arithmetic as well.

However, we have all the tools necessary to prove the following quite remarkable fact.

This theorem brings together elements from all of our study of proofs so far. We have both types of quantifiers, as well as some significant assumptions (as part of an implication). We even used the GCD Characterization Theorem for a key step in our proof. Finally, this proof introduced one more useful kind of structure: a subproof, or proof of a smaller claim that is used to prove the main result. Just as helper functions help organize a program, small claims and subproofs help organize a proof so that each part can be understood separately, before being combined into a whole.We can outline the previous proof in three steps: (1) Prove that \(\gcd(a, p) = 1\), (2) Prove that \(\exists k \in \Z,~ ak \equiv 1 \MOD p\), and (3) Prove that \(\exists k' \in \Z,~ ak' \equiv b \MOD p\). As your proofs grow longer and longer, make good use of this approach to keep your proofs readable and easy to understand. There is nothing worse than having to slog through pages and pages of a single proof without any sense of what claim is being proved, and how the claims fit together.

Proof by contradiction

The final proof technique we will cover in this chapter is the proof by contradiction. Given a statement \(P\) to prove, rather than attempt to prove it directly we assume that its negation \(\NOT P\) is true, and then use this assumption to prove a statement \(Q\) and its negation \(\NOT Q\). We call \(Q\) and \(\NOT Q\) the contradiction that arises from the assumption that \(P\) is .

Why does this work? Essentially, we argue the if \(P\) is false, then statement \(Q\) must be true, but its negation \(\NOT Q\) must also be true. But these two things can’t be true at the same time, and so our original assumption must be wrong!

Proofs by contradiction are a more general form of the indirect proof-by-contrapositive we saw earlier in this chapter. They often take a bit more thought because it isn’t necessarily clear what the contradiction (statement \(Q\)) should be. We finish off this chapter by presenting one particularly famous proof by contradiction dating back to the Greek mathematician Euclid.Although Euclid’s original proof was written in an informal style, the idea was certainly there.

The principle of induction

Let us start with an example.

It is not hard to show that this is true without using induction for \(n=2\) as follows. By assumption, \(x \equiv y \MOD m\), and therefore \(x \cdot x \equiv y \cdot y \MOD m\), and thus \(x^2 \equiv y^2 \MOD m\).This is Part 3 of Example 2.19 from the previous chapter. In order to show that it is true for \(n=3\), we can argue that since we already know that \(x^2 \equiv y^2 \MOD m\), and \(x \equiv y \MOD m\), then \(x \cdot x^2 \equiv y \cdot y^2 \MOD m\) and thus \(x^3 \equiv y^3 \MOD m\). Then we can prove that it is true for \(n=4\) in exactly the same way, and so on. But in order to make the “and so on” mathematically rigorous, we need to use induction.

The first explicit formulation of the principle of induction was given by Pascal (as in Pascal’s triangle) in 1665. However, its uses have been traced as far back as Plato (370 BC), and a variation of Euclid’s proof of the existence of infinitely many primes (from around the same time period). We cannot stress enough the importance of the induction principle—it is the powerhorse behind nearly all proofs. The principle of induction applies to universal statements over the natural numbers—that is, statements of the form \(\forall n \in \N,~ P(n)\). It cannot be used to prove statements of any other form! Note however that \(P(n)\) can be quite complicated and can involve other possibly nested quantifiers.

In this course, we will study only the most basic form of induction, commonly called simple induction.In CSC236, you’ll learn about different forms of induction. There are two steps to using this induction principleNotice that the two steps are a conjunction, so they may be presented in either order. Variable names (\(n\), \(k\), \(i\), etc.) are up to you, provided you use each name to refer to a fixed value:

• The base case is a proof that the statement holds for the first natural number, \(0\); that is, a proof that \(P(0)\) holds.
• The inductive step is a proof that for all \(n \in \N\), if \(P(n)\) is true, then \(P(n+1)\) is also true. That is: \[\forall n \in \N,~ P(n) \IMP P(n+1).\]

Once the base case and inductive step are proven, by the principle of induction, one can conclude \(\forall n \in \N,~ P(n)\).

The point behind induction is that sometimes it isn’t possible to give a direct proof for all \(n\) at once—sometimes we require knowing that the statement is true for smaller values in order to show that it is true for larger ones. Induction formalizes this idea—if you show it is true for the smallest element (the base case) and if you can show that as long as it is true for \(n\) then it is also true for the number right after \(n\), then we can conclude that it is true for every \(n\).

Why does the principle of induction work? This is essentially the domino effect. Assume you have shown the base case and the inductive step. In other words, you know \(P(0)\) is true, and you know that \(P(n)\) implies \(P(n+1)\) for every natural number \(k\). Since you know \(P(0)\) from the base case and \(P(0) \IMP P(1)\) by the inductive step, we have \(P(1)\). Then since you now know \(P(1)\) and \(P(1) \IMP P(2)\) from the inductive step, we have \(P(2)\). Now since we know \(P(2)\) and \(P(2) \IMP P(3)\), we have \(P(3)\). And so on.

Examples from number theory

Let us see how to use induction to prove some statements from number theory.

Let’s do another example, which is quite similar to the previous one, but is useful for practicing this new technique.

Now let us go back to our motivating example and prove it using induction.

One interesting subtlety in how we set up this proof is in how we chose the order of the variables \(m, x, y, n\) being quantified. You know already that changing the order of these variables doesn’t change the meaning of the statement, because they are all universally-quantified. However, changing their order does change the proof that we would write!

A different way to proceed in this proof would be to write the statement as \[\forall n \in \N,~ \forall m, x, y \in \N,~ x \equiv y \MODS m \IMP x^n \equiv y^n \MODS m.\] Doing it this way, we would define \(P(n)\) to be the (more complex) statement \[\forall m,x,y \in \N,~ x \equiv y \MODS m \IMP x^n \equiv y^n \MODS m.\] If we had proceeded this way, then the base case, \(P(0)\) of the induction would be prove the implication for all values of \(m,x,y\) when \(n=0\). So in the base case we would first fix particular but arbitrary values of \(m,x,y \in \N\) before proceeding with the proof. And again in the inductive step, we would need to prove \(P(n)\) implies \(P(n+1)\), which is a more complicated statement since the other variables \(m,x,y\) are not fixed but are universally quantified. When we have a universal statement such as this one that involves one universally quantified variable that we want to do induction on (in this case \(n\)), plus other universally quantified variables that we do not need to do induction on (in this case \(m,x,y\)), it is usually easier to first fix \(m,x,y\) and then do induction on \(n\), as we did above, rather than the other way around.Remember that we can reorder consecutive variables with the same quantification in a statement without changing the meaning.

We will do one more example from number theory. This example is proving an inequality rather than an equality, and demonstrates how to use induction with a different starting number as the base case.

Combinatorics

Combinatorics is an area of mathematics concerned with counting objects, and more generally with analyzing patterns. A pattern is most typically a sequence of numbers and we will often want to derive a closed-form expression for \(a_k\), the \(k^{th}\) number in the sequence, or for \(\sum_{i=0}^k a_i\), the sum of the first \(k+1\) numbers in the sequence.Drawing inspiration from programming, sequence indexing starts at \(0\), not \(1\).

Incorrect proofs by induction

Just as it is important to be able to formulate a correct proof by induction, it is equally important to not be fooled by an incorrect proof! Consider this well-known example. Say we want to prove that all jellybeans have the same colour. Let \(P(n)\) be the statement that any set of \(n\) jellybeans all have the same colour. The base case is when there is only one jellybean, and it has one colour, so the statement \(P(1)\) is true.

Now let’s assume that \(P(k)\) is true and try to prove that \(P(k+1)\) is true. Let \(S = \{j_1, j_2, \dots, j_{k+1}\}\) be a set of \((k+1)\) jellybeans. Consider the first \(k\) jellybeans in \(S\): \(S_1 = \{j_1, \dots, j_k\}\). By the induction hypothesis, they all must have the same colour. Now consider the last \(k\) jellybeans in \(S\): \(S_2 = \{j_2, \ldots, j_{k+1}\}\). Again by the induction hypothesis, they must also have the same colour. Now since these two sets overlap, the two colours must be the same, thus the entire set \(j_1,\dots, j_{k+1}\) of jellybeans has the same colour and we can conclude \(P(k+1)\).

We know that it is clearly wrong, so where exactly is the mistake? To find the error it is helpful to walk through the smallest possible counterexample—say for instance we have two jellybeans, where the first one is red and the second one is yellow. In this case we can see the mistake since the two sets \(S_1\) and \(S_2\) do not overlap.

Looking ahead: strong induction (optional)

The way that we expressed the induction principle above was to prove the base case \(P(0)\), and then give a general argument for \(P(n+1)\) assuming \(P(n)\). We said intuitively that this works by the domino effect: (1) Suppose we know that the first domino \(P(0)\) is down, and (2) we know that as long as \(P(n)\) is down, then so is \(P(n+1)\), then this implies (3) that all of the dominoes are down. However, we could have replaced (2) by (2’) which states that as long as all of the first \(n\) dominoes are down, \(P(0),\ldots,P(n)\), then so is \(P(n+1)\). As long as we know (1) and (2’), this still implies (3). Note that proving (2’) rather than (2) may be easier since we can assume not only that \(P(n)\) is true, but that all of \(P(0),P(1),\ldots,P(n)\) are true, in order to deduce that \(P(n+1)\) is true.

This is called the principle of strong induction. It turns out that strong induction and simple induction (the form we’ve been using in this chapter) are equivalent, but sometimes it can be easier to prove a statement using strong induction rather than simple induction. More formally, suppose that we want to prove \(\forall n \in \N,~ n \geq k \IMP P(n)\), where \(k\) is some natural number. The principle of strong induction can be used to prove this statement as follows.

• First, prove the base case \(P(k)\).
• Secondly, prove that for any fixed but arbitrary \(n \geq k\), \(P(j)\) for all \(j\), \(k \leq j \leq n\) implies \(P(n+1)\).

Then we can conclude \(\forall n \in \N,~ n \geq k \IMP P(n)\). You will learn more about strong induction in CSC236/240.

Note that in this last example, it would have been futile to try to use simple induction since then we would only know that \(n\) is a product of prime numbers, which is useless in order to show that \(n+1\) is the product of prime numbers.After all, when \(n \geq 2\), we know that \(n\) is not a factor of \(n+1\).

Decimal representation of natural numbers

When you read a number such as “\(324\)” in decimal, you see a sequence of decimal digits, \(d_{k-1} d_{k-2} \dots d_1 d_0\), where each digit \(d_i\) is in \(\{0, 1, 2, \dots, 9 \}\). The number that corresponds to this sequence of digits is \(\sum_{i=0}^{k-1} d_i \times 10^i\). In words, the right-most digit is multiplied by \(10^0\), the next digit to the left is multiplied by \(10^1\), and so on. Each digit to the left has a multiplier that is \(10\) times the multiplier of the previous digit. In our example “\(324\)”, we have \(d_2=3\), \(d_1=2\), and \(d_0=4\), and so the value is \(3 \times 10^2 + 2 \times 10^1 + 4 \times 10^0\).

Here are some useful properties of decimal representation:

1. To multiply a number by \(10\), you can just insert a \(0\) at the right end of its decimal form. That is, if a number \(n\) is represented by \(d_{k-1} d_{k-2} \dots d_1 d_0\), then the representation of \(10\times n\) is \(d_{k-1} d_{k-2} \dots d_1 d_0 0.\) For example, \(10 \times 324\) is represented as \(3240\).

2. With the \(k\) decimal digit positions, exactly \(10^k\) unique numbers (from \(0\) to \(10^k-1\)) can be represented. For example, using three decimal digits (\(k=3\)), we can represent the numbers \(0\) through \(999\).

Binary representation of natural numbers

The binary (base \(2\)) representation of a number uses the binary digits \(\{0, 1\}\) instead of the ten decimal digits \(\{0,1,2,\dots,9\}\) We write numbers in binary in the same sort of way that we write numbers in our traditional base 10 system. Again we represent a number by a sequence of binary digits, \(d_{k-1} d_{k-2} \dots d_1 d_0\), but now each digit \(d_i\) is \(0\) or \(1\). The value of the number corresponding to this sequence is: \(\sum_{i=0}^{k-1} d_i \times 2^i\). Note that the change in the expression is the change from powers of \(10\) to powers of \(2\). The number represented in its decimal form as \(139\) would represented in binary as: \(1 \times 2^7 + 1 \times 2^3 + 1 \times 2^1 + 1 \times 2^0 = 10001011\). In the sum, the terms multiplied by the digit \(0\) were omitted. The rightmost digit is multiplied by \(2^0=1\), the next to the left is multiplied by \(2^1=2\), and so on. Each digit to the left has a multiplier that is 2 times the previous digit. The above properties about decimal representation continue to hold, but now the \(10\)’s are replaced by the new base, \(2\). Finally, we note that when discussing the binary representation of a number, the digits \(d_i\) are often called bits. To the right are some examples of numbers together in their decimal and binary representation.

Properties of binary representation

Our first theorem shows that every natural number has a binary representation. We label the digits \(b_i\) since the base is \(2\), which makes the digits bits.

One troubling issue with the representations that result from the statement of the previous theorem is that they are not unique.Remember that the existential quantifier says that at least one value of the domain satisfies a given property; not that exactly one does. For example, the decimal number \(14\) can be represented in binary as \(1110\), but it can also be represented as \(01110\), \(001110\), \(0001110\) and so on. Computer scientists hate to have multiple ways to represent a particular entity, since each different representation can lead to a case to check. We want a rule that forces us to say which of those representations for \(14\) is the agreed upon unique representation. How can we choose? One way is to say that we want the one that does not have the uninformative leading \(0\)’s.

A motivating example

Consider the following function, which prints out all the items in a list:

def print_items(lst: list) -> None:
    for item in lst:
        print(item)

What can we say about the running time of this function? An empirical approach would be to measure the time it takes for this function to run on a bunch of different inputs, and then take the average of these times to come up with some sort of estimate of the “average” running time.

But of course, given that this algorithm performs an action for every item in the input list, we expect it to take longer on longer lists, so taking an average of a bunch of running times loses important information about the inputs.This is like doing a random poll of how many birthday cakes people have eaten without taking into account how old the respondents are.

How about choosing one particular input, calling the function multiple times on that input, and averaging those running times? This seems better, but even here there are some problems. For one, the computer’s hardware can affect running time; for another, computers all are running multiple programs at the same time, so what else is currently running on your computer also affects running time. So even running this experiment on one computer wouldn’t necessarily be indicative of how long the function would take on a different computer, nor even how long it would take on the same computer running a different number of other programs.

While these sorts of timing experiments are actually done in practice for evaluating particular hardware or extremely low-level (close to hardware) programs, these details are often not helpful for the average software developer. After all, most software developers do not have control over the machine on which their software will be run.

So rather than use an empirical measurement of runtime, what we do instead is use an abstract representation of runtime: the number of “basic operations” an algorithm executes. However, there is a good reason “basic operation” is in quotation marks—this vague term raises a whole slew of questions:

• What counts as a “basic operation”?
• How do we tell which “basic operations” are used by an algorithm?
• Do all “basic operations” take the same amount of time?

The answers to these questions can depend on the hardware being used, as well as what programming language the algorithm is written in. Of course, these are precisely the details we wish to avoid thinking about.

For example, suppose we analyzed the running time of the print_items function, counting only the print calls as basic operations. Then for a list of length \(n\), there are \(n\) print calls, so we would say that the running time of print_items on a list of length \(n\) is \(n\) basic operations.

But then a friend comes along, and says “No wait, the variable item must be assigned a new value of the list at every loop iteration, and that counts as a basic operation.” Okay, so then we would say that there are \(n\) print calls and \(n\) assignments to item, for a total running time of \(2n\) basic operations for an input list of length \(n\).

But then another friend chimes in, saying “But print calls take longer than variable assignments, since they need to change pixels on your monitor, so you should count each print call as \(10\) basic operations.” Okay, so then there are \(n\) print calls worth \(10n\) basic operations, plus the assignments to item, for a total of \(11n\) basic operations for an input list of length \(n\).

And then another friend joins in: “But you need to factor in an overhead of calling the function as a first step before the body executes, which counts as \(1.5\) basic operations (slower than assignment, faster than print).” So then we now have a running time of \(11n + 1.5\) basic operations for an input list of length \(n\).

And then another friend starts to speak, but you cut them off and say “That’s it! This is getting way too complicated. I’m going back to timing experiments, which may be inaccurate but at least I won’t have to listen to these increasing levels of fussiness.”

The expressions \(n\), \(2n\), \(11n\), and \(11n + 1.5\) may be different mathematically, but they share a common qualitative type of growth: they are all lines, i.e., grow linearly with respect to \(n\). What we will study in the next section is how to make this observation precise, and thus avoid the tedium of trying to exactly quantify our “basic operations,” and instead measure the overall rate of growth in the number of operations.

Asymptotic growth

Here is a quick reminder about function notation. When we write \(f : A \TO B\), we say that \(f\) is a function which maps elements of \(A\) to elements of \(B\). In this chapter, we will mainly be concerned about functions mapping the natural numbers to the nonnegative real numbers,These are the domain and range which arise in algorithm analysis—an algorithm can’t take “negative” time to run, after all. i.e., functions \(f: \N \TO \R^{\geq 0}\). Though there are many different properties of functions that mathematicians study, we are only going to look at one such property: describing the long-term (asymptotic) growth of a function. We will proceed by building up a few different definitions of comparing function growth, which will eventually lead into one which is robust enough to be used in practice.

Unfortunately, absolute dominance is too strict for our purposes: if \(g(n) \leq f(n)\) for every natural number except \(5\), then we can’t say that \(g\) is absolutely dominated by \(f\). For example, the function \(g(n) = 2n\) is not absolutely dominated by \(f(n) = n^2\), even though \(g(n) \leq f(n)\) everywhere except \(n = 1\). Here is another definition which is a bit more flexible than absolute dominance.

Intuitively, “dominated by up to a constant factor” allows us to ignore multiplicative constants in our functions. This will be very useful in our running time analysis because it frees us from worrying about the exact constants used to represent numbers of basic operations: \(n\), \(2n\), and \(11n\) are all equivalent in the sense that each one dominates the other two up to a constant factor.

However, this second definition is still a little too restrictive, as the inequality must hold for every value of \(n\). Consider the functions \(f(n) = n^2\) and \(g(n) = n + 90\). No matter how much we scale up \(f\) by multiplying it by a constant, \(f(0)\) will always be less than \(g(0)\), so we cannot say that \(g\) is dominated by \(f\) up to a constant factor. And again this is silly: it is certainly possible to find a constant \(c\) such that \(g(n) \leq cf(n)\) for every value except \(n = 0\). So we want some way of omitting the value \(n = 0\) from consideration; this is precisely what our third definition gives us.

Intuitively, this definition allows us to ignore “small” values of \(n\) and focus on the long term, or asymptotic, behaviour of the function. This is particularly important for ignoring the influence of slow-growing terms in a function, which may affect the function values for “small” \(n\), but eventually are overshadowed by the faster-growing terms. In the above example, we knew that \(n^2\) grows faster than \(n\), but because an extra \(+ 90\) was added to the latter function, it took a while for the faster growth rate of \(n^2\) to “catch up” to \(n + 90\).

Our final definition combines both of the previous ones, enabling us to ignore both constant factors and small values of \(n\) when comparing functions.

One special case of Big-Oh: \(\cO(1)\)

So far, we have seen Big-Oh expressions like \(\cO(n)\) and \(\cO(n^2)\), where the function in parentheses has grown to infinity. However, not every function takes on larger and larger values as its input grows. Some functions are bounded, meaning they never take on a value larger than some fixed constant.

For example, consider the constant function \(f(n) = 1\), which always outputs the value \(1\), regardless of the value of \(n\). What would it mean to say that a function \(g\) is Big-Oh of this \(f\)? Let’s unpack the definition of Big-Oh to find out.

\[\begin{align*} & g \in \cO(f) \\ & \exists c, n_0 \in \R^+,~ \forall n \in \N,~ n \geq n_0 \IMP g(n) \leq c \cdot f(n) \\ & \exists c, n_0 \in \R^+,~ \forall n \in \N,~ n \geq n_0 \IMP g(n) \leq c \tag{since $f(n) = 1$} \end{align*}\]

In other words, there exists a constant \(c\) such that \(g(n)\) is eventually always less than or equal to \(c\). We say that such functions \(g\) are asymptotically bounded with respect to their input, and write \(g = \cO(1)\) to represent this.

Omega and Theta

Big-Oh is a useful way of describing the long-term growth behaviour of functions, but its definition is limited in that it is not required to be an exact description of growth. After all, the key inequality \(g(n) \leq c f(n)\) can be satisfied even if \(f\) grows much, much faster than \(g\). For example, we could say that \(n + 10 \in \cO(n^{100})\) according to our definition, but this is not necessarily informative.

In other words, the definition of Big-Oh allows us to express upper bounds on the growth of a function, but does not allow us to distinguish between an upper bound that is tight and one that vastly overestimates the rate of growth.

In this section, we will introduce the final new pieces of notation for this chapter, which allow us to express tight bounds on the growth of a function.

You can think of Omega as the dual of Big-Oh: when \(g \in \Omega(f)\), then \(f\) is a lower bound on the growth rate of \(g\). For example, we can use the definition to prove that \(n^2 - 5 \in \Omega(n)\).

We can now express a bound that is tight for a function’s growth rate quite elegantly by combining Big-Oh and Omega: if \(f\) is asymptotically both a lower and upper bound for \(g\), then \(g\) must grow at the same rate as \(f\).

Properties of Big-Oh, Ometa, and Theta

If we had you always write chains of inequalities to prove that one function is Big-Oh/Omega/Theta of another, that would get quite tedious rather quickly. Instead, in this section we will prove some properties of this definition which are extremely useful for combining functions together under this definition. These properties can save you quite a lot of work in the long run. We’ll illustrate the proof of one of these properties here; most of the others can be proved in a similar manner, while a few are most easily proved using some techniques from calculus.We discuss the connection between calculus and asymptotic notation in the following section, but this is not a required part of CSC165.

Back to algorithms

Let us return to our example at the beginning of the chapter:

def print_items(lst: list) -> None:
    for item in lst:
        print(item)

How can we use our asymptotic notation to help us analyze the running time of this algorithm? Remember that we have proposed expressions like \(n\), \(2n\), \(11n\), \(11n + 1.5\), where \(n\) is the length of the input list.

By using asymptotic notation, we no longer need to worry about the constants involved, and so don’t need to worry about whether a single call to print counts as one or ten “basic operations.” Moreover, by focusing on the long-term growth, we can also ignore lower-order terms like the \(1.5\) in \(11n + 1.5\).The formal grounding for this is in the section of properties of Theta.

Just as switching from measuring real time to counting “basic operations” allows us to ignore the computing environment in which the program runs, switching from an exact step count to asymptotic notation allows us to ignore machine- and programming language-dependent constants involved in the execution of the code.

Having ignored all these external factors, our analysis will concentrate on how the size of the input influences the running time of a program, where we measure running time just using asymptotic notation, and not exact expressions.

Warning: the “size” of the input to a program can mean different things depending on the type of input, or even depending on the program itself. Whenever you perform a running time analysis, be sure to clearly state how you are measuring and representing input size.

Because constants don’t matter, we will use a very coarse measure of “basic operation” to make our analysis as simple as possible. For our purposes, a basic operation (or step) is any block of code whose running time does not depend on the size of the input.To belabour the point a little, this depends on how we define input size. For integers, we usually will assume they have a fixed size in memory (e.g., 32 bits), which is why arithmetic operations take constant time. But of course if we allow numbers to grow infinitely, this is no longer true, and performing arithmetic operations will no longer take constant time.

This includes all primitive language operations like most assignment statements, arithmetic calculations, and list and string indexing. The one major statement type which does not fit in this category is a function call—the running time of such statements depends on how long that particular function takes to run. We’ll revisit this in more detail later.

def print_sums(lst: list) -> None:
    for item1 in lst:
        for item2 in lst:
            print(item1 + item2)

def f(lst: List[int]) -> None:
    for item in lst:
        for i in range(10):
            print(item + i)

def combined(lst: list) -> None:
    # Loop 1
    for item in lst:
        for i in range(10):
            print(item + i)
    # Loop 2
    for item1 in lst:
        for item2 in lst:
            print(item1 + item2)

def all_pairs(lst: list) -> None:
    i = 0
    while i < len(lst):
        j = 0
        while j < i:
            print(i + j)
            j = j + 1
        i = i + 1

def uses_helpers(lst: list) -> None:
    x = helper1(lst)
    y = helper2(lst)
    return x + y

def is_prime(n: int) -> bool:
  if n < 2:
    return False

  d = 2
  while d < n:
    if n % d == 0:
      return False   # Since d divides n, n cannot be prime.
    d = d + 1

  return True   # If the loop doesn't find a divisor, n is prime.

def print_primes(n: int) -> None:
    for k in range(2, n + 1):
        if is_prime(k):
            print(k)

def twisty(n: int) -> None:
  x = n
  while x > 1:
    if x % 2 == 0:
      x = x / 2
    else:
      x = 2*x - 2

Worst-case and best-case running times

In the previous section, we saw how to use asymptotic notation to characterize the rate of growth of the number of “basic operations” as a way of analyzing the running time of an algorithm. This approach allows us to ignore details of the computing environment in which the algorithm is run, and machine- and language-dependent implementations of primitive operations, and instead characterize the relationship between the input size and number of basic operations performed.

However, this focus on just the input size is a little too restrictive. Even though we can define input size differently for each algorithm we analyze, we tend not to stray too far from the “natural” definitions (e.g., length of list). In practice, though, algorithms often depend on the actual value of the input, not just its size. For example, consider the following function, which searches for an even number in a list of integers.

def has_even(numbers: List[int]) -> bool:
    for number in numbers:
        if number % 2 == 0:
            return True
    return False

Because this function returns as soon as it finds an even number in the list, its running time is not necessarily proportional to the length of the input list.

The running time of a function can vary even when the input size is fixed. Or using the notation of the previous section, the inputs in \(\cI_{has\_even, 10}\) do not all have the same runtime. The question “what is the running time of has_even on an input of length \(n\)?” does not make sense, as for a given input the runtime depends not just on its length but on which of its elements are even.

And because our asymptotic notation is used to describe the growth rate of functions, we cannot use it to describe the growth of a whole range of values with respect to increasing input sizes. A natural approach to fix this problem is to focus on the maximum of this range, which corresponds to the slowest the algorithm could run for a given input size.

Note that \(WC_{func}\) is a function, not a (constant) number: it returns the maximum possible running time for an input of size \(n\), for every natural number \(n\). And because it is a function, we can use asymptotic notation to describe it, saying things like “the worst-case running time of this function is \(\Theta(n^2)\).”

The goal of worst-case runtime analysis for func is to find an elementary function \(f\) such that \(WC_{func} \in \Theta(f)\).

However, it takes a bit more work to obtain tight bounds on a worst-case running time than on the runtime functions of the previous section. Let’s think about just the worst-case running time for now. It is difficult to compute the exact maximum number of basic operations performed by this algorithm for every input size, which requires that we identify an input for each input size, count its maximum number of basic operations, and then prove that every input of this size takes at most this number of operations. Instead, we will generally take a two-pronged approach: proving matching upper and lower bounds on the worst-case running time of our algorithm.

Don’t assume bounds are tight!

It is likely unsatisfying to hear that upper and lower bounds really are distinct things that must be computed separately. Our intuition here pulls us towards the bounds being “obviously” the same, but this is really a side effect of the examples we have studied so far in this course being rather straightforward. But this won’t always be the case: the study of more complex algorithms and data structures exhibits quite a few cases where obtaining an upper bound involves a completely different argument from a lower bound.

Let’s look at one such example that deals with manipulating strings.

def palindrome_prefix(s: str) -> int:
  n = len(s)
  for prefix_length in range(n, 0, -1):  # goes from n down to 1
    # Check whether s[0:prefix_length] is a palindrome
    is_palindrome = True
    for i in range(prefix_length):
      if s[i] != s[prefix_length - 1 - i]:
        is_palindrome = False
        break

    # If a palindrome prefix is found, return the current length.
    if is_palindrome:
      return prefix_length

Average-case analysis

So far, we have only been concerned with the extremes of algorithm analysis. However, in practice this type of analysis sometimes ends up being misleading, with a variety of algorithms and data structures having a poor worst-case performance still yet performing well on the vast majority of inputs.

Some reflection makes this not too surprising; focusing on the maximum of a set of numbers says very little about the “typical” number in that set, or, more precisely, nothing about the distribution of numbers in that set.

A bit more concretely, suppose we have an algorithm func, and we look at the set of running times \[Times_{func,n} = \{ \text{running time of executing \texttt{func(x)}} \mid x \in \cI_{func,n} \}.\] We have seen that we define the worst-case running time with the maximum running time in this set.Don’t forget that the worst-case running time is a function that uses not just one but all of the \(Times_{func,n}\) sets. Our final topic of this chapter will be to look at another measure of the running time: taking the average of the numbers in this set.

def search(lst: List[int], x: int) -> bool:
    for item in lst:
        if item == x:
            return True
    return False

Initial definitions

Let us start with some basic definitions.

The conventional notation to introduce a graph is to write \(G = (V, E)\), where \(G\) is the graph itself, \(V\) is its vertex set, and \(E\) is its edge set.

Intuitively, the set of vertices of a graph represents a collection of objects, and the set of edges of a graph represent the relationships between those objects. For example, if we wanted to use the terminology of graphs to describe Facebook, we could say that each Facebook user is a vertex, while each friendship between two Facebook users is an edge between the corresponding vertices.

We often draw graphs using dots to represent vertices, and line segments to represent edges. We have drawn some examples of graphs below.

Now that we have these definitions in hand, let us prove our first general graph property. Unlike the previous example, here we will not have a concrete graph to work with, but instead have to work with an arbitrary graph.Reading this, you should immediately expect to see a universal quantification over the set of all possible graphs.

Paths and connectedness

Often when we use graphs in modelling the real world, it is not sufficient to capture just a single relationship between entities. Our goal now is to use individual edges, which represent some sort of relationship between vertices, to build up extended, indirect connections between vertices. In a social network, for example, we want to be able to go from friends to “friends of friends,” and even “friends of friends of friends of friends.” In a graph representing roads between cities, we want to be able to go from “a route between cities using one road” to “a route between cities using \(k\) roads.” We use the following definitions to make precise these notions of “indirect” relationships.

Being connected is a fundamental property of graphs. Imagine, for example, a geographical representation where each graph vertex is a city, and each edge a road between two cities. If this graph is not connected, then there is at least one pair of cities for which it is not possible to get from one to the other by road.

Now let us look at one extremely useful property of connectedness: the fact that if two vertices in a graph are both connected to a third vertex, then they are also connected to each other.

A limit for connectedness

Intuitively, since connectivity is based on paths between vertices, which in turn are built from edges, it is natural to think that we can “force” a graph to be connected by simply adding more edges to it. In this section, we will investigate this by trying to answer the question: “how many edges does it take to ensure that a graph is connected?”

The previous example shows the danger of making statements using existential quantifiers: often it is easy to prove that a particular value exists, but what we really care about is the “best” possible value. We don’t want just any \(M\), but the smallest possible one which forces a graph to be connected. For instance, it would be much more interesting if we could prove the following statement, with \(M = 2n\): \[\forall n \in \Z^+,~ \forall G = (V, E),~ (|V| = n \AND |E| \geq 2n) \IMP \text{$G$ is connected}.\]

Unfortunately, this statement is false, and in fact the value \(M = 2n\) is not even close, as we’ll prove next.

We have now proved that a graph with a fairly large number of edges can still not be connected. It is worth noting that \(\frac{(n-1)(n-2)}{2} = \frac{n(n-1)}{2} - (n - 1)\). That is, there is a graph that is missing only \(n - 1\) edges from the set of all possible of edges, but is still not connected. The question becomes: can we go higher still? Is it possible for a graph on \(n\) vertices to have more than \(\frac{(n-1)(n-2)}{2}\) edges and yet still be not connected? Or is the best possible \(M\) from our original question indeed \(\frac{(n-1)(n-2)}{2} + 1\)?

It turns out that the latter is true, and this will be the last, and most challenging, proof we do in this section.

Cycles and trees

We spent the last section investigating how many edges a graph would need to force it to be connected.Or, how many edges are sufficient for graph connectedness. We will now turn to the dual question: how many edges is a graph forced to have if it is connected?Or, how many edges are necessary for graph connectedness. Rather than taking a graph and adding edges to it to see how far we can go without it becoming connected, we now ask how many edges can we remove from a connected graph without disconnecting it.

We might consider some simple examples to gain some intuition here. For example, suppose we have a graph with \(n\) vertices which is just a path.

This has \(n - 1\) edges, and if you remove any edge from it, the resulting graph will be disconnected (we leave a proof of this as an exercise).

But this isn’t the only possible configuration for such a graph. The one on the right certainly isn’t a path; you may recognize it as a “tree,” though we won’t define this term formally until later in this chapter.

Indeed, removing any edge from this graph disconnects it, and you might notice by counting that the number of edges is again one fewer than the number of vertices.

It turns out that these examples do give us the right intuition: any connected graph \(G = (V, E)\) must have \(|E| \geq |V| - 1\).The contrapositive is also an interesting statement: if a graph has fewer than \(|V| - 1\) edges, it cannot be connected. The tricky part is proving this. Once again, we must struggle with the fact that even though the previous examples gave us some intuition, it is a challenge to generalize these examples to obtain an argument that works on all graphs satisfying these vertex and edge counts.

To get a formal proof, we’ll need some way of characterizing exactly when we can remove an edge from a graph without disconnecting it. The following definition is an excellent start.

In other words, a cycle is like a path, except it starts and ends at the same vertex. The length of a cycle is the number of edges used by the sequence, which is also the number of distinct vertices in the sequence (the above notation describes a cycle of length \(k\)). Cycles must have length at least three; two adjacent vertices are not considered to form a cycle.

To use our example of cities and roads, if there is a cycle in the graph, it is possible to make a trip which starts and ends at the same city, and travels no road or city more than once.

Getting back to our motivation, cycles are a form of “connectedness redundancy” in a graph. Vertices in a cycle are all obviously connected to each other, but even if one edge is removed, the result is a path. In this case, the cycle’s vertices are still connected to each other—albeit with possibly a much longer path to travel. Even though the diagrams on the right illustrate this property for a cycle itself, we will now show that this property holds even when this cycle is part of a larger graph.

This example tells us that if we have a connected graph with a cycle, it is always possible to remove an edge from the cycle and still keep the graph connected. Since we are interested in talking about the minimum number of edges necessary for connecting a graph, we’ll now think about graphs which don’t have any cycles.

We would like to say that trees are the “minimally-connected” graphs: that is, the graphs which have the fewest number of edges possible but are still connected. It may be tempting to simply assert this based on the definition and what we have already proven, but let \(G\) be a connected graph, and consider the following statements carefully:

1. If \(G\) has a cycle, then there exists an edge \(e\) in \(G\) such that \(G - e\) is connected.
2. If \(G\) is a tree, then it does not have a cycle.
3. If \(G\) does not have a cycle, then there does not exist an edge \(e\) in \(G\) such that \(G - e\) is connected.

We know that (1) is true by the previous example. (2) is true simply by the definition of “tree.” How do we know (3) is true?

In fact, we don’t. The statements (1) and (3) may look very similar, but they are not logically equivalent. In fact, (3) is logically equivalent to the converse of (1): if we let \(P\) be the statement “\(G\) has a cycle” and \(Q\) be the statement “there exists an edge \(e\) in \(G\) such that \(G - e\) is connected,” then (1) is simply \(P \IMP Q\), while (3) is \(\NOT P \IMP \NOT Q\).

So we actually need to prove (3) directly, which is what we’ll do next.

Thus we now can state and prove the following fact about trees.

We can say that a tree is the “backbone” of a connected graph. While a connected graph may have many edges and many cycles, it is possible to identify an underlying tree structure in the graph that, if it remains unchanged, ensures the graph remains connected, regardless of any other edges removed.In fact, many such trees may exist. This insight is the basis of minimum spanning trees, a well-studied problem in computer science that you will learn about in future courses.

Now, let us return to our original motivation of counting edges to prove the following remarkable result, which says that the number of edges in a tree depends only on the number of vertices.

With this lemma in hand, we can now give a complete proof of the number of edges in a tree. The key will be to use induction, removing from the original graph a vertex with just one neighbour, so that the number of edges also only changes by one. But how can we use induction on a statement that starts with \(\forall G = (V, E)\)? We are used to seeing induction used with a statement of the form \(\forall n \in \N\) or \(\forall n \in \Z^+.\) To this end, we introduce a variable \(n\) to stand for the number of vertices in a graph, and then apply induction using the number of vertices. The statement that we will prove becomes \[\forall n \in \Z^+,~ \forall G = (V, E),~ (\text{$G$ is a tree} \AND |V| = n) \IMP |E| = n - 1.\]

Combining everything together, we can conclude the following required number of edges for any connected graph.

Since every connected graph contains at least one tree (just keep removing edges in cycles until you cannot remove any more), this constraint on the numbers of edges in a tree translates immediately into a lower bound on the number of edges in any connected graph (in terms of the number of vertices of that graph).

Rooted trees

The definition of “tree” that we have used so far—a connected graph with no cycles—is actually more general than what you may be familiar with from typical computer science applications. This is because trees themselves do not enforce an orientation or ordering amongst vertices, while in practice almost all of their uses involve a notion of hierarchy that elevates some vertices above others.

For this type of application, we specialize our more general definition to add this notion of hierarchy. Note that this definition is a “cosmetic” one in the sense that it does not actually say anything different about the structure of a graph, but merely how we interpret the vertices of the graph.

Simply by designating one vertex in a tree as special, we immediately obtain a sense of direction in the tree; we can now use distance from the root as a partial ordering of the vertices, and talk about moving “away from the root” or “towards the root” when traversing edges. We typically represent this sense of direction visually by drawing rooted trees with the root vertex at the top, although of course this is merely a convention.

We will now introduce some new terminology that emerge naturally from this orientation. Note that much of the terminology matches our intuition for relationships among relatives in a family tree.

We have already studied the relationship between the numbers of vertices and edges in connected graphs. This question is far less interesting when it comes to trees, because there is an exact relationship between the number of vertices and edges in a tree (\(|E| = |V| - 1\)).

But for rooted trees, we get another fundamental relationship to study: how the number of vertices influences the height of the tree. This is a question which is fundamental to many computer science applications of rooted trees, which typically traverse a tree by starting at its root and going down. Such algorithms take a longer amount of time depending on how tall the tree is.

What is more interesting, and what is often done in practice, is to try to restrict the structure of a rooted tree by restricting the number of children each vertex can have. The following definition is one of the most common such restrictions.

Our last proof in this course is captures one such relationship between height and number of vertices in binary rooted trees.

Turing’s legacy: the limitations of computation

What are the limits of computation? Are there functions that we want to get a computer to calculate but that are beyond the capability of computers? This abstract and fuzzy question was formalized precisely by Alan Turing even before computers were invented! Namely, he defined a Turing machine, which is a purely mathematical model of computation. It is simple enough to reason about, yet powerful enough to capture any conceivable computational device!

After defining Turing machines, Turing proved that there are important problems that cannot be computed by any Turing machine. Because of the universality of the Turing machine, this then implies that these problems cannot be solved on any computer!

Before we try to explain the main ideas behind the proof, we would like to point out that mathematical expression is fundamental to even formulate the question. The abstraction of computation via the mathematical Turing machine model is essential to express a statement that talks about whether a given function can be computed.

The most famous problem that cannot be solved by any Turing machine (and thus by any computer) is called the Halting Problem. Informally, the input to the Halting Problem is a program, \(P\), written in some programming language, together with an input to the program, \(x\). The Halting Problem should output True for the pair \((P,x)\) if and only if program \(P\) halts on input \(x\).By halt we mean that if we had an infinite amount of memory, then running \(P\) on \(x\) would eventually stop—that is, it would not get into any infinite loops. The obvious way to try to solve the Halting Problem on input \((P,x)\) is to simply run or simulate \(P\) on the input \(x\) and see what happens. If \(P\) does halt on \(x\), then our simulation will also halt and we will eventually discover that \(P\) halts on \(x\). But what happens when \(P\) does not halt on \(x\)? In this case we are in trouble! What Turing proved is that it is basically impossible for a computer program to figure out with certainty whether an arbitrary program \(P\) will halt on a particular input \(x\).This is a worst-case result: there is no procedure that can decide for all programs \(P\) and for all inputs \(x\) whether or not \(P\) halts on \(x\). But in special cases, it may be easy to determine what will happen. That is, there is no clairvoyant way to examine a program to determine whether not it will halt on an input. Essentially the only thing that one can do is to run the program and see what happens.

We will focus on decision problems; that is, on problems that compute functions \(f\) from the natural numbers to \(\{0,1\}\). Since we want to prove a negative result, we can pick any problem that we’d like, so we aren’t cheating by focusing on decision problems.Indeed, decision problems turn out to be powerful enough anyway! That is, for any \(f : \N \to \N\), there is a corresponding decision problem such that this problem can be computed if and only if the original function \(f\) can be computed. Furthermore, we will assume that the input to our decision problem is encoded in binary, so the input is just some finite-length string of zeroes and ones, and the output is either zero (False) or one (True). We are going to try to explain the main ideas behind the halting problem without getting into too much notation.

First, we have to define our formal model of computation, the Turing machine (TM). We won’t go into any details of Turing machines. They are a beautiful abstraction of computation, but these details aren’t really necessary to understand the main thing that we want to prove in this chapter—that certain natural and important functions are beyond the power of computation. The only thing that you will need to know about Turing machines is that they are just programs in a simple programming language where we will assume an unbounded amount of computational memory. If \(M\) is a TM for computing a decision problem, it takes as input an arbitrary natural number, encoded by a binary string, \(s\). For each \(s\), the TM may or may not halt on \(s\). If it does halt, then it outputs either zero (reject) or one (accept). Turing machines satisfy the following important properties:

1. Turing machines are a universal model of computation—any program written in any standard programming language can be converted to an equivalent Turing machine (TM) program.

2. Turing machines can be enumerated.By enumerated we mean that there is an algorithm that on input \(i\) can output the first \(i\) TM’s, \(M_1\), \(M_2\), , \(M_i\).

Both of these properties are not unreasonable—if you think of your favorite programming language, such as Python, it should be clear that both of these properties hold.

The first main idea is to come up with one explicit decision problem that cannot be computed by a TM. This first problem will not be the Halting Problem but will instead be a problem that we will construct to make the proof easier for us.The proof method is called diagonalization, and was first used by Cantor in order to argue there is no bijective mapping from the natural numbers to the real numbers. By property (2) above, TM programs can be enumerated, so let us write them as \(M_1,M_2, \dots\), where \(M_i\) is the \(i^{th}\) TM in the enumeration. Now consider the following decision problem, called \(\cD\) (for the diagonal language): The input to \(\cD\) is, as usual, a natural number \(i\) (encoded in binary). The output is \(1\) if either \(M_i\) does not halt on input \(i\), or if \(M_i\) halts and outputs \(0\) on input \(i\). Otherwise, if \(M_i\) halts and outputs \(1\) on \(i\), then \(D\) on \(i\) outputs \(0\). In other words, \(\cD\) does the opposite of what \(M_i\) does on input \(i\)—if \(M_i\) rejects \(i\) (either by not halting or by halting and not accepting), then \(\cD\) accepts \(i\), and if \(M_i\) accepts input \(i\), then \(\cD\) rejects \(i\). The very cool thing is that we can prove that the decision problem \(\cD\) is not computed by any TM! Why is this? We want to prove that for every \(j \in \N\), that \(M_j\) does not compute \(\cD\). So fix some arbitrary \(j \in \N\), and consider \(M_j\) on input \(j\)—by construction it does the opposite thing that \(\cD\) does on input \(j\), and therefore \(M_j\) does not compute \(\cD\). Since we have proven this for every \(j\), it follows that there is no Turing machine that computes \(\cD\)!The main point here is that the set of all functions from the natural numbers to \(\{0, 1\}\) is huge—much, much larger than the set of all Turing machines since we have assumed that they can be enumerated Thus, at a high level the idea is the same as Cantor’s, but here we are showing that there is no bijective mapping from the set of all TM’s to the set of all such functions.

Okay, so thus far we have found one explicit decision problem, \(\cD\), that cannot be computed by any TM. Now we want to prove that some specific decision problem (the Halting Problem) also cannot be computed by any TM. At this point, we need to be more precise about what we mean by the Halting Problem. We define the Halting Problem \(\cH\), as follows. The input is a pair \((i,j)\) where both \(i\) and \(j\) are natural numbers. The output should be \(1\) (accept) if \(M_i\) halts on input \(j\), and should be \(0\) (reject) otherwise.But we said that inputs should be single numbers and not pairs of numbers! To handle this, we can encode a pair of numbers \((i, j)\) by the single number \(2^i \times 3^j\). Check that \(i\) and \(j\) can be uniquely extracted from \(2^ \times 3^j\).

To show that \(\cH\) is not computable by any TM, we will introduce a second idea called a reduction that is extremely powerful and used extensively in Computer Science. In fact, you’ve seen this idea already although it didn’t have this fancy name—it is none other than a proof by contradiction. Say that we want to prove \(\NOT A\), and we already know \(\NOT B\). Suppose that we can prove \(A \IMP B\). Then assume for sake of contradiction that \(A\) is true, thus by modus ponens it follows that \(B\) is true, which contradicts \(\NOT B\). To instantiate this in our setting, we let \(B\) be the statement that \(\cD\) is computable by some TM, and let \(A\) be the statement that \(\cH\) is computable by a TM. Since we have already proven \(\NOT B\), it is just left to prove \(A \IMP B\); that is, we want to prove that if \(\cH\) is computable by a TM, then \(\cB\) is also computable by a TM, in order to get a contradiction and therefore conclude that \(\cH\) is not computable. For this choice of \(A\) and \(B\), proving \(A \IMP B\) is called a reduction (from \(B\) to \(A\)) because we are showing that computing \(B\) essentially reduces to the task of computing \(A\).

So our remaining task is therefore to show that if we can compute \(\cH\), then we can compute \(\cD\) by a TM. Here we will have to wave our hands a little bit, since we haven’t even formally defined Turing machines! But we did say that they satisfy property (1), and thus we will argue informally that if we have an algorithm for \(\cH\), then we can also construct an algorithm for \(\cD\). How would we compute \(\cD\) in the first place? Remember that the input is a number \(i\), and we want to determine of \(M_i\) halts and accepts \(i\). The first step on input \(i\) is to actually find the TM program \(M_i\). This can be carried out by enumerating all TMs until we get to the \(i^{th}\) one.This is very inefficient by it will suffice for our purposes here. There are much more efficient ways to do this.

Now that we have \(M_i\), how can we tell if \(M_i\) accepts \(i\)? If we just simulate \(M_i\) on input \(i\), we may run into a problem if \(M_i\) doesn’t halt on \(i\) since in that case our simulation will run forever and we will never know when to stop the simulation and output \(1\). But we are saved by the fact that we are assuming that we have an algorithm for \(\cH\)! Thus we can first run the algorithm for \(\cH\) on the input pair \((i,i)\). If it accepts, then we know that \(M_i\) halts on \(i\), so in this case we can go ahead and simulate \(M_i\) on \(i\), and return the opposite answer. If on the other hand the algorithm for \(\cH\) on \((i,i)\) rejects, then we know that \(M_i\) does not halt on \(i\), so we should just return \(1\) (and not bother to do the simulation). Thus informally we have argued that if \(\cH\) is computed by some TM, then \(\cD\) is also computed by some TM, so we can conclude that \(\cH\) is not computable!

Gödel’s legacy: the limitations of proofs

Another very famous problem that is not computable is called the Entscheidungsproblem.Entscheidung is the German word for “decision.” Informally, this is the problem of determining whether or not a mathematical statement is valid. We start with a fixed set of axioms (such as the axioms of Peano arithmetic, the most standard set of axioms for reasoning in number theory). The input is a mathematical sentence \(s\), and the output should be \(0\) (reject) if \(s\) is not a logical consequence of the axioms, and \(1\) (accept) if \(s\) is a logical consequence of the axioms. This problem is undecidable by Matiyasevich’s theorem, since the existence of solutions for Diophantine equations are a special type of mathematical statement. However, it is also possible give a simpler reduction showing that the Entscheidung problem is undecidable. Philosophically this is quite interesting as it proves that mathematics cannot be fully automated.

Closely connected to the Entscheidung problem is Hilbert’s second problem, to prove that the axioms of arithmetic are consistent. In 1931 Kurt Gödel proved his famous incompleteness theorems, essentially showing that there is no reasonable set of axioms that can captureBy “capture” we mean that the set of sentences that are logically consequences of the axioms should be exactly those sentences that are true over the natural numbers. all sentences that are true about the natural numbers. While his proof did not mention anything about computers or computability, we now know that his theorems are in fact very closely connected to undecidability, and can be proven using the ideas of reductions.

P versus NP

In the 60’s and 70’s, the complexity class \(\cP\) emerged. It captures those decision problems that can be computed efficiently—where the number of basic computation steps in order to arrive at the answer is at most polynomial in the input length. That is, the runtime is \(n^{O(1)}\). There are many examples of important problems in \(\cP\) and you will study them in many of your courses. For example all of these problems have polynomial-time algorithms: detecting whether a graph contains a cycle, determining whether a graph contains a perfect matching, and computing the greatest common divisor of two numbers. A larger class of decision problems is known as \({\cal NP}\)\({\cal NP}\) stands for nondeterministic polynomial time and contains important problems such as whether a graph contains a clique of size \(n/2\), and whether there is a boolean assignment to the variables of a propositional formula forcing it to true. \({\cal NP}\)-complete problems are the hardest problems in the class \({\cal NP}\) and the best algorithms for these problems run in time that is exponential in \(n\)—that is, in time \(2^{O(n)}\). The class \({\cal NP}\) is very important because it contains many many important problems that range across all disciplines, including fundamental problems in computational biology, physics, machine learning, and of course computer science. For all of these problems, all known algorithms run in exponential time, which makes them completely infeasible to solve. On the other hand, it is not known if it is possible to solve these problems much more efficiently, say in polynomial time. The \(\cP\) versus \({\cal NP}\) problem is the open problem of whether or not any of the \({\cal NP}\)-complete problems can be solved in polynomial time, and is one of the most important open problems in mathematics and computer science today.It turns out that if one can get a polynomial-time algorithm for any \({\cal NP}\)-complete problem, then all problems in \({\cal NP}\) also have efficient algorithms. This was proving by Cook and independently by Levin in the early 70’s.

Other cool applications: Cryptography

As we mentioned in the introduction to these notes, cryptography is the study of algorithms and protocols for doing cool things across the Internet in the presence of adversaries. The techniques and tools that have been developed in cryptography are often very surprising and incredibly creative. Cryptography is in some sense the flip side of complexity theory. Whereas lower bounds in complexity theory prove that certain problems are inherently hard in that they require an infeasible amount of time in order to solve, cryptography uses this hardness in order to develop protocols! That is, who are these adversaries anyway? They are people or other computers, and thus they are limited to performing polynomial-time computation. In cryptography, the computational hardness of problems is used to an advantage—to build protocols for various tasks, where the security of the protocols can be proven under the assumptions that the adversaries are polynomially-bounded, and that certain problems in complexity theory are infeasible.