Proofs go Poof

This week's topics included a conclusion of proofs and the beginning of algorithms.

Proof by cases, the last method of proofs we learnt, involves  breaking the problem down into different cases or situations and then solving for each case, ultimately bringing the problem back circle and joining up the conclusions. We wrapped up proofs with a summary of introduction and elimination rules for the basic proof conditions.

Then we started on the more...computer science side of things. Chapter 4, "Algorithm Analysis and Asymptotic Notation", which is basically about the classification of algorithms by their big O notation. It is about how efficiently an algorithm(a set of problem solving steps) works. We started off with bubble and merge sort, comparing the difference between their run times given the same set of data for both sorts. In computer science the point to be noted is that run time isn't actually about the seconds that the program takes to complete its job. Rather, it is about the number of steps that the program has to run and how that number changes with respect to the actual code of the algorithm and the kind of input or data it has to work with. This makes it independent of the hardware it is being run on.

Another thing to note is that constants do not matter in determining run time. 2n and 2000n still have the same linear runtime. Furthermore, when it comes to large data sets, the lower order terms become irrelevant for the run time. Something like n² + 2n + 3, is pretty much the same as n² because the 2n + 3 is tiny in size compared to the n² which makes it have little no effect on the run time.

The asymptotic notation to depict run times is O(f(n)), whereas the exact form is actually the function f(n ) in its entirety. This brought us to the end of the class with a brief look on worst, average, and best case scenarios for an algorithm, with worst case meaning under what data conditions does the algorithm have the longest run time and best case meaning under what data conditions it has the best run time.