Induction

Finally, we are introduced to Induction in this class. I don't really understand why we were not introduced to introduction when we were first doing proofs, given that it is so useful. Actually, induction seems so simple and straightforward that its power is sometimes underestimated at first. At least I was one of them. However, upon closer examination, I realized that induction actually proves some of our assumptions in our previous proofs. For example, one of our first proofs was "for all natural numbers n, if n is odd, then n^2 is odd." We proved that by first assuming that n is a natural number and n is odd. How do we know that if n is odd then n^2 is odd is true for all natural numbers? Do we plug every natural number in and check the result? We could do that until the end of time, and still be unable to get a conclusion. Therefore, we need a more powerful tool of logic to help us out.

Induction is really an axiom, and like all axioms, it is self evident. Lets break it down.

• let P(n) be a predicate
• if P(0) is true and for all natural numbers n, (P(n)=>P(n+1)) is true
• then for all natural numbers n, P(n) is true!

So if P(0) is true, and P(0) => P(1) is true, then P(1)=> P(2) is true, and P(2) => P(3) is true... and so on...

Now lets prove the following proposition:

It's interesting to note, that I didn't really introduce anything new here... We were already given the equation sum of i = n(n+1)/2, and we simply proved that it's true. However, induction did not give us that equation nor did it give us the reasoning behind it. Is that satisfying?

Visualizing Big-O

When first introduced to the formal definition of Big-O, -Omega, and -Theta, it can be a little daunting to absorb everything and understand them. At least I admit that I was overwhelmed by all of the information. So how does one compartmentalize these definitions, and use them for algorithm analysis and proofs?

I don't think there is only one way, instead different people learn through different techniques. However, what works for me is to visualize the definitions in terms of graphs rather than focus on the definitions, which express the same information anyways. For Big-O, I imagine two curves that grow in different rates, and a point on the x-axis as the 'breakpoint', such that beyond that point, one curve is always slower at growth than the other. It goes to reason that that curve is in the Big-O of the faster growing curve.

Now that we understand Big-O, the scaffold is set, and we can easily understand Big-Omega, with just one minor alteration. Instead of saying that the slower curve is in Big-Omega, we say that the faster curve is in Big-Omega. That effectively makes the curve an upper-bound. Finally, Big-Theta is simply the conjunction between Big-O and Big-Omega.

As mentioned before, we use Big-O notation to help us explain the complexity of an algorithm. In reality, we want algorithms that run in O(n) or O(log n), and never O(n^2) or O(n^3), because the run-time would grow exponentially based on n.