The Big O - Insertion Sort Worst Case Scenario

The Big O - Insertion Sort Worst Case Scenario

    To begin, this is my interpretation of how the Big O proof works. As our focus this week was on the Big O, so will my slog be to try to better understand the concept. What we were looking at was the worst case scenario of using insertion sort on an array and the number of iterations the worst case scenario would fall in-between. As the proof goes, we would B have some value such that n or the length of our array A would be greater or equal to B. This would then imply that W of n is less than or equal to some value of c times n squared for the upper bound of the range and greater than or equal to some value of c times n squared for the lower bound of the range. From here, based on our code we overestimated the upper boundary and underestimated the lower boundary to be sure that the worst case scenario would fall within these two values. Its taken some thinking to get used to the idea but I've come to understand it.

     I'm quite curious as to how the average case and best case scenarios would work now. I've really been enjoying this class and have been thinking more and more about continuing further in this sub-field of computer science. The whole algorithmic analysis concept really intrigues me and I must say that this is probably my favorite course that I'm currently taking.