CSC165: SLOG - Asymptotics [Big-Oh] ---------Course Notes Chapter 5 ---------------------[ Week 9 ]

This week's lectures opened up with sorting strategies, introducing insertion & selection sort. To properly introduce these algorithms Danny opened up by using these methods to sort a hand of cards. I must say that the moment he asked the class, what type of sorting method each of one us prefers to use, I had an overwhelming urge to shout out "BUBBLE-SORT!!", unfortunately I didn't do so, though it would've been an interesting topic to speak upon.

Next topic was the big-Oh definition, not too much to say here, simply that the definition states, in terms of limits, if n approaches infinity, the function f(n) will be no bigger than c(g(n)), once the appropriate c is found. Big-Oh is quite straight forward. After the introduction of this definition Danny followed with a proof of a function being no bigger than another function or in other words the first function is bounded above by the second. I compared the proof done with the evening section and the suggestion made for the afternoon section was much more complicated, I see the reason why Danny suggested everyone to take a look at the evening section and it's to show that there is, I suppose in my personal understandings, an easier/simpler method, and that we should strive for the simplest solution.

Afterward, the disproof followed and soon l'Hopital was introduced to aid in the explanation of the disproof. I wasn't exactly too sure, but I believe the purpose of l'Hopital was to show that the property (2^n)/(n^2) works to infinity and by using l'Hopital to show this, it works that for all n that property is > c (where c can be any real number[+]). My question is, if this is true, does that mean we have to show l'Hopital for each proof? Or was that just an in depth explanation to why this disproof is true?

Nevertheless, that was Week 9!, only 3 more weeks to go... :( university years sure pass by quickly...