CPSC 121 Lecture Notes - Lecture 23: Binary Search Tree, Modus Ponens, Universal Instantiation

• School: UBC
• Department: Computer Science
• Course: CPSC 121
• Professor: BELLEVILLE, PATRICE

Document Summary

Cpsc 121 lecture #23 algorithm efficiency, more on predicates. Topics included: algorithm efficiency and run times, negation law, predicate negations, universal transformations. Sometimes, a(n) isn"t smaller than cb(n), but a(n) cb(n) for all n when n is bigger than a certain values: e. g. let a(n) be n, and let b(n) be n2. For positive values smaller than 1, n is bigger than n2, but for all other values, n2 is bigger than n. therefore, we would set n0 to be 1. Common run times (remember that o(n) is for the worst case scenario): n = 1, e. g. return the first element of a list of inputs, log(n, e. g. Find a number in a binary search tree: n, e. g. print out each item of a list, nlog(n, n2, e. g. the number of swaps needed to order n numbers in increasing order, 2n.