CSC165H1 Study Guide - Insertion Sort, Precondition

• School: UTSG
• Department: Computer Science
• Course: CSC165H1
• Professor: Nathalie Fournier

Document Summary

Due: by 3 pm on tuesday august 7: the following is one of possible implementation of insertion sort: # precondition: a is a list of n numbers and n = len(a) for i in 0, 1, , n-1: for j in i-1, i-2, , 0: if a[j] < a[j+1]: tmp = a[j] Give a tight bound on the worst-case running time of the above algorithm, and write a detailed proof that your bound is correct. Let us call the worst-case runtime for the above algorithm w (n). This is equivalent to saying that w (n) o(n2) w (n) (n2), so we can prove both parts separately. W (n) o(n2) c r+, b n, n n, n b w (n) cn2. Let i be a set of valid inputs to the algorithm. Let t(x) be the time taken by the algorithm on an input x. (note: this nomenclature is standard in this course, so it can be used without explicit introduction).