CSC165H1 Lecture 1: week9

• School: UTSG
• Department: Computer Science
• Course: CSC165H1
• Professor: any

Document Summary

We say (cid:1859) is absolutely dominated by (cid:1858) We say (cid:1859) is eventually dominated by (cid:1858) We say (cid:1859) is eventually dominated up to a what factor by (cid:1858) Ex (cid:1858)(cid:4666)(cid:4667)= (cid:1858)(cid:4666)(cid:4667) (cid:1859)(cid:4666)(cid:4667) (cid:883)(cid:882)(cid:882) (cid:1858)(cid:4666)(cid:4667) (cid:1859)(cid:4666)(cid:4667) (cid:1859)(cid:4666)(cid:4667)=(cid:885)+(cid:883) (cid:1858)(cid:4666)(cid:4667) (cid:1859) is eventually dominated up to a constant factor by (cid:1858) A short way of saying "(cid:1859) is eventually dominated up to a constant by (cid:1858)" is (cid:1859) is big oh off. Small (cid:1841)(cid:4666)(cid:1858)(cid:4667)={(cid:1859)|(cid:1859):(cid:1840) (cid:2868) (cid:1853)(cid:1856) (cid:1855)(cid:2869)(cid:2868) + (cid:1840) (cid:3410)(cid:2868) (cid:1859)(cid:4666)(cid:4667)(cid:3409)(cid:1855)(cid:1858)(cid:4666)(cid:4667)} (cid:862)the step count of may algorithm is (cid:885)+(cid:884) (cid:1841)(cid:4666)(cid:4667)" Let (cid:1853),(cid:1854) +, the following are true: if (cid:1853)> and (cid:1854)>, then log(cid:1853) (cid:1841)(cid:4666)log(cid:1854)(cid:4667, if (cid:1853)(cid:3409)(cid:1854). Then (cid:3028) (cid:1841)(cid:4666)(cid:3029)(cid:4667: if (cid:3409)(cid:1853)(cid:3409)(cid:1854), then (cid:1853)" (cid:1841)(cid:4666)(cid:1854)(cid:4667, if (cid:1853)>, then log(cid:1853) (cid:1841)(cid:4666)(cid:3029)(cid:4667)(cid:4666)(cid:1854)(cid:4667) if (cid:1853)>. Ex log(cid:884) (cid:4666)(cid:1841)(cid:2868). (cid:2868) . (cid:2868). (cid:2869)(cid:4667) (cid:2869)(cid:2868)(cid:2868)(cid:2868)(cid:2868)(cid:2868)(cid:2868) (cid:1841)(cid:4666)(cid:883). (cid:882)(cid:882) (cid:882)(cid:883)(cid:4667) (cid:2868). (cid:2868)(cid:2868)(cid:2868)(cid:2868)(cid:2869) (cid:1841)(cid:4666)log(cid:884)(cid:4667) (cid:2868). (cid:2868)(cid:2868)(cid:2868) (cid:1864)(cid:1857)(cid:1853) (cid:2869) (cid:885)+(cid:883). (cid:885)(cid:882)(cid:882) (cid:2869). (cid:2868)(cid:2868)(cid:2868)(cid:2868)(cid:2869) (cid:2870) . (cid:2871)