COMP 250 Lecture Notes - Lecture 11: Selection Sort, List Of Association Football Teams To Have Won Four Or More Trophies In One Season
19 Feb 2017
School
Department
Course
Professor
Document Summary
In the worst case, takes t(n) = 1 + 15n + 5n2 primitive operations. When n is large, t(n) = 5n2. When n becomes large, doubling n quadruples t(n); this is true for any coefficient of n2. Describes how running time of an algorithm increases as a function of n (size of problem) when n is large. Gets rid of terms that become insignificant when n is large. Will say things like: worst case running time of selectionsort on an array of n elements is. O(n2: worst care running time of mergesort on an array of n elements is. Let f(n) and g(n) be two non-negative (don"t take negative values) functions defined on the natural numbers f(n) typically a complicated function, describes number of operations. We say f(n) is o(g(n)) is and only if there exists an integer n0 and a real number c such that for all n>= n0, f(n)
