Week 7: :O :O :O

This week we finished up proof techniques and moved on to program complexity, mainly big O and the number of steps of an algorithm.

This is the first real thing that relates mathematical reasoning to computer science, which makes it interesting for me. Since my old brick / laptop was rather slow and outdated, I understand well the importance of running time analysis. I still find it strange that big O ignores constant factors and lower order terms, so that 100000n^3 + n is considered the same as 0.1n^3, even though in "real running time", this makes a difference (at least it did on my brick). I guess the key thing to be aware of is not to confuse the number of steps of a program with the time the program takes to run on some hardware. The same program will be slow on a slow computer and fast on a fast computer, but the running time does not differ between computers and is not measured as units of time, but as units related to the number of steps, determined solely based on the algorithm. Specifically, running time looks at how quickly the number of steps carried out by the algorithm grows as the input size grows. Relating this to real life, often we want to look through a large number of items in a short time, such as when you google "computer science" and google proudly reports that it found about 272,000,000 results in 0.52 seconds. When we are calculating the number of steps for large input sizes, only the highest order term matters, and the rest only contribute a small difference. Therefore, it is more useful to say that 100000n^3 + n grows no faster than n^3, asymptotically.

I guess now we're going to have to prove that some algorithm is O(n)? Nooooooooooooooooooooooo..............