Theory of Algorithms

The following are certain revelations I had. Related: NP Completeness

Recursive functions can be linear!

A function that divides and conquers can be linear. Consider one that splits its input into halves, and works on one half. It then splits that part into half, and works one half of that. That approximates to

N + N/2 + N/4 + ... 1 = 2N

That is O(N), or linear. Quicksort is O(nlgn), where lgn is log base 2, but it splits the input and works on both halves. Consult the master theorem, or use your intuition. Although there are lgn stages, the number of elements per stage decreases exponentially. This 'cancels' the lgn factor, if you'd like. Just think of the series.

Proofs by induction

The idea: You have a formula. Show that it works for the base case. Then, assume the formula is true for some value N. Now show that the formula works for the next case (N+1) as well (use the fact that it works for N). For example, we wish to prove that our function f(k) is equal to g(k).

First, show that f(0) = g(0) [the base case].
Now, show that f(k + 1) = g(k +1) [rewrite g(k+1) so it equals f(k +1). We assume that g(k) = f(k), that the formula is true for the current case].
Thus, the statement f(k) = g(k) is true. f(1) = g(1) from above. Thus, f(2) = g(2) from just now. Continue to infinity, so f(n) = g(n).

More generally, you are proving a proposition P(k + 1). You can assume P(k) is true to help rewrite the current situation as P(k + 1). (Induction.html)

Main idea: "The proposition is true in the first instance. And if a given instance is true, the next one in the sequence will also be true. Then the proposition will be true in all instances." (UnderstandingInduction.html)