COMPSCI 61B Lecture Notes - Lecture 32: Total Order, Antisymmetric Relation, Big O Notation
1 Jun 2017
School
Department
Course
Professor
Document Summary
Midterm 2 grades will be out late tuesday/early wednesday. Grading is e ectively done, but some makeups tomorrow. A sort is a permutation (re-arrangement) of a sequence of elements taht brings them into order according to some total order. Total: x <= y or y <= x for all x, y. Antisymmetric: x <= y and y <= x i x = y (x and y are equivalent) Transitive: x <= y and y <= z implies x <= z. Unequal items may be equivalent" under these de nitions. Inversion: a pair of elements that are out of order. Given a sequence of elements with z inversions. Perform a sequence of operations that reduces inversions to 0. Characterizations of the runtime e ciency are sometimes called the time complexity of an algorithm. Ex: dfs has time complexity theta(v + e) Characterizations of the extra memory usage of an algorithm is sometimes called the space complexity of an algorithm.
