CS 2305 Lecture 16: CS 2305 Lecture 16
30 Oct 2018
School
Department
Course
Professor
Document Summary
Bigomega hcgcx f t g be functions from the set of integers or the set let of real numbers to the set of real numbers we say fcx is. Sorting based on comparison is nch tog n logba ogob. Ex showthat fcx 8 3 5 47 is r x3. 8 3 5 77 is f x also 043. Xz i c 1000 k l f x is 0cg x andif fcx is hcg x fad is ga. I 1213 1 tn is m2 we proved before fan is 0w need to show fan is a h2. Ex fix 3 48 1ogx is 01 2. X s i x i if fcx is 0cgcx gex is effcx. Yes fcx anx an x 1 19x 1do is g xn c 11 k i c 3 k i fail_ocr fix d r. 2h12 2n1111 0 n worst case worst case general 2i12 comparisons if average i2 is i i.
