CSC263H1 Lecture Notes - Lecture 12: Sorting Algorithm, Binary Tree, Information Theory
18 Oct 2017
School
Department
Course
Professor
Document Summary
Csc 263 lecture summary for week 12 winter 2017. Existence of algorithms that run in worst-case time o(n log n) confirm sorting can be done in time o(n log n), but does not rule out existence of other algorithms that might do better. We know how to analyse worst case complexity of algorithms. Worst case complexity of _problems_ involves additional work. For problem p, c(p) = best (minimum) worst-case running time of any algorithm that solves p. Upper bound on c(p): give an algorithm and analyse its runtime. How to prove _every_ algorithm requires a certain amount of time? In practice, prove lower bounds on class of algorithms: consider only algorithm of a particular kind. Example: binary search in a[13], returning index of x (or 0 if not found): x <= a[2] T/ \f x <= a[1] x <= a[3] A[1] <= x a[2] <= x a[3] <= x 0. Internal node (node with children) = comparison performed by algo.
