Using Mathematical Proofs to Compare Algorithms

Algorithms!! They can be surprisingly useful … hey? From https://practicalmotoring.com.au/

As you journey through your exploration of math. You will come across Algorithms.

If you are unfamiliar with algorithms consider checking this link out, It’s a pretty short read (3 mins) and you may find that they are easier to come to terms with.

Algorithm — a well-specified procedure of doing computation on a set of input to get an output

With algorithms being procedures for getting outputs from inputs often times one will need to compare between a number of algorithms for which one would be best in order to do this you will most likely need to prove that one algorithm has better complexity than another usually,time complexity a fancy phrase for how many instructions will your algorithm take to complete?

need to prove that one algorithm has better complexity than another

In order to go about proving this, most often we will go about using Mathematical proofs to show this, this article is intended as an introduction to a few basic mathematical proofs

• Direct Proof
• Proof by Contradiction
• Proof by Induction
• Proof by Contrapositive

What! what! what! what!

Relax most of these are just fancy words for very direct procedures let’s explore them

Direct Proof

We use direct proof in a sequence of statements which are either true or false from previous statements, and whose last statement is the conclusion to be proved.

Most direct proofs are written in English with words such as “if … then”.

Illustration on how we apply direct proof: “The date on the tickets say the festival is tomorrow, so the festival is not today.”

Proof by Contradiction

We start this with a basic assumption, that a statement is trueor false but not both!

We get a contradiction when we can show that a statement is both true and false hence invalidating our initial assumption

Illustration: Suppose N is the greatest integer. Then, add 2 to N. Now, N +2 must be the greatest integer. So, N can’t be the greatest integer.

Illustration1: At 1:00 pm there were no burgers available at art cafe, but later you decide to go there physically and you find out that art cafe indeed has some burgers available. So we can’t say that art cafe doesn’t have any burgers.

Proof by Induction

We use proof by induction to show an infinite number of facts by:

• showing that a specific case holds
• Then using the assumption that if the case holds for a certain value then it also holds for the value before the special case and the value after the special case …

Real life illustration: You are in line at KFC. The first person in line orders a cheesy crunch burger. Also, if the person in front of you orders a cheesy crunch burger, you order it too, because it sounds so good.

Proof by Contrapositive

The contrapositive of a statement is formed by negating both terms and reversing the direction on negation. Therefore the contrapositive of the statement “if A, then B” is “if not B, then not A.”

A statement and its contrapositive are logically equivalent: if the statement is true, then its contrapositive is true, and vice versa.

Illustration: If the moon is made of burgers, human beings can fly. (The statement is TRUE since the moon is not made of burgers and human beings can’t fly.)

Would you use proofs to compare algorithms?

Back to proving 🎲