Asymptotics

Table of contents

1. Reasoning about Big-O proofs
2. Big-Theta proofs
3. Three-way merge sort
4. Proof guidelines
   1. Disproof
   2. Negation
   3. Backwards reasoning

Submit your solutions to the following 3 questions as a PDF on Gradescope.

Reasoning about Big-O proofs

The following Big-O proofs are incorrect. For each proof, briefly explain why it is incorrect. The claims these proofs are trying to prove are true. Only the proofs themselves are incorrect.

1. Let \(f(N) = N^3 + N\). We want to prove that \(f(N) \in O(N^3)\). By the definition of Big-O, \(f(N) \in O(N^3)\) if and only if \(f(N) \leq k_2 \cdot N^3\) for some \(k_2 > 0\) and all \(N \geq N_0\). Using the definition of \(f(N)\), \(N^3 + N \leq k_2 \cdot N^3\). Let \(k_2 = 2\) and \(N_0 = 1\). By substituting in, we have \(N^3 + N \leq 2N^3\). So, subtracting an \(N^3\) from both sides, we get \(N \leq N^3\). Dividing by \(N\) for both sides, we get \(1 \leq N^2\), which is true for all \(N \geq N_0\). Therefore, \(f(N) \in O(N^3)\).
2. We want to disprove that \(N^4 \in O(N^3)\). For this claim to be true, it must be the case that \(N^4 \leq k_2 \cdot N^3\) for some \(k_2 > 0\). But \(N^4 \leq N^3\) can never be true because the 4 exponent causes \(N^4\) to always be larger than \(N^3\). Thus, \(N^4 \notin O(N^3)\).

Big-Theta proofs

Use the formal definition of Big-Theta to prove or disprove each claim. You should assume that the domain and co-domain of \(N\) are the natural numbers. To disprove a claim, negate the quantified statement and prove the negation. Make sure you are not using backwards reasoning. Do not use calculus, i.e. do not use limits, differentiation, integrals, etc.

1. \(2^{N + 3} \in \Theta(2^N)\)

2. \(2^{N / 3} \in \Theta(2^N)\)

   Note: This is significantly harder than claim 1.

Three-way merge sort

Consider the following variant of merge sort. Instead of splitting the list into two halves, split it into three thirds. Then, recursively sort each third and merge the three sorted sublists.

def mergesort3(A):
    N = len(A)
    if N <= 1:
        return A
    K = math.ceil(N / 3)
    M = math.ceil(N / 3 * 2)
    return merge3(mergesort3(A[0:K]), mergesort3(A[K:M]), mergesort3(A[M:N]))

def merge3(L0, L1, L2):
    return merge(L0, merge(L1, L2))

Assume that merge merges two sorted lists of lengths \(\ell_1\) and \(\ell_2\) in \(\Theta(\ell_1 + \ell_2)\) time. To simplify notation, you may assume that \(N\) is a power of three.

1. Give a tight asymptotic runtime bound for merge3(L0, L1, L2), if L0, L1, and L2 are three sorted lists each of length \(N / 3\).
2. Let \(T(N)\) denote the running time of mergesort3 on an array of size \(N\). Give a base case and a recurrence for \(T(N)\). Use variables such as \(c_0, c_1, c_2\) as necessary.
3. Give a tight asymptotic runtime bound for mergesort3 by finding a closed-form solution for \(T(N)\). Show your work.

Proof guidelines

Good proofs are clear, easily followed, and easily confirmed by your reader.

Disproof

Occasionally, we don’t want to prove something is true. Instead, we want to disprove it. This is more tricky of a problem than it seems, as we cannot just show that a proof trying to show that statement is true doesn’t work—what if some other approach had worked? Proofs are reserved for true statements—even a proof by contradiction is ultimately proving that some statement is true because the alternative would be ridiculous, i.e. it can’t be false.

Negation

Suppose we had the claim that “All apples are green.” This is not a true statement, but suppose someone had tried to tell us that all apples were green. The intuitive disproof of this fact is to give an example of an apple which is not green: one can do this simply by producing a red apple and saying “See, here is an apple which is not green. Therefore, it can’t be true that all apples are green.”

Breaking this down, there are two things that are really going on here. First, we assume that the statement “All apples are green” cannot be both true and false. (Recall that this is called the Law of Excluded Middle.) Second, we negate the statement “All apples are green” to “Some apples are not green” or “At least one apple is not green,” and prove that some apples are not green by producing an example of an apple which is not green, such as a red apple. These two things imply that the original statement must be false, which is a disproof. So, in order to disprove a statement, we prove that the negation is true!

Backwards reasoning

The following line of reasoning is almost always wrong.

And so because we see that this statement is true, the original statement must have been true!

What has likely happened is that we have shown that a statement is consistent rather than correct. While a correct statement is always true, a consistent statement only holds under assumption of the preceding statements.

This pattern of reasoning is known as backwards reasoning: when we attempt to prove a statement by assuming that it is true and then proving another statement. Backwards reasoning can lead to complete nonsense.

1. \(4 \geq 5\)
2. \(4 * 0 \geq 5 * 0\) (Multiply both sides by 0)
3. \(0 \geq 0\) (QED)

We can’t actually prove that 4 is greater than or equal to 5, but backwards reasoning has led us to this conclusion! An indicator that we’ve done something wrong is that the proof begins with the claim we wanted to prove and ends with something else.

In order to develop a correct proof, it’s oftentimes helpful to develop scratch work from what we want, transform it into what we have, and approach the problem from a different angle. If the proof is actually bogus, this will not work at all.

1. \(0 \geq 0\)
2. \(0 / 0 \geq 0 / 0\) (To reverse multiplying by 0, divide by 0)
3. \(4 \geq 5\)

Here, it becomes clear that we’ve done some total nonsense and divided by 0 to get our result. Our scratch work is not reversible, so our backwards proof was completely bogus and we can’t save any of it.

Now that we know about backwards reasoning, try applying it to the following example.

Prove that if positive integer \(x\) is greater than or equal to 5, then \(x^2 - 2x + 1 \geq 16\)

We could start from \(x \geq 5\), and attempt to deduce the goal, but it’s hard to see what operations to perform from this position. Instead, on a piece of scratch paper, it could be helpful to start from our goal.

1. \(x^2 - 2x + 1 \geq 16\)
2. \((x - 1)^2 \geq 16\) (Factoring)
3. \(x - 1 \geq 4\) (Square root both sides)
4. \(x \geq 5\) (Add one to both sides)

Note

We are not done at this point! This uses backwards reasoning.

While this is not a valid proof, this scratch work has some good ideas that provide insight into what we might need to do. Assuming that nothing has gone wrong, let’s reverse the steps:

1. \(x \geq 5\)
2. \(x - 1 \geq 4\) (Reverse add: Subtract one from both sides)
3. \((x - 1)^2 \geq 16\) (Reverse square root: Square both sides)
4. \(x^2 - 2x + 1 \geq 16\) (Reverse factoring: Multiply out the left hand side)

After confirming that each step is valid, this is a sufficient proof for the statement since it starts from what we know and ends in what we wished to show.