I&C SCI 46 Lecture Notes - Lecture 8: Complexity Class, Priority Queue, Sorting Algorithm

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

In this lecture we will learn how to compute the complexity class of all the code in a function (and therefore the complexity class of the function) by using simple rules for composition. We will see how apply these rules in various functions and combinations of functions in classes using the lens of analysis of algorithms, and compare fundamentally different algorithms for solving the same problem. Next, we will compare some time and space metrics for array vs. linked list implementations of simple data types (e. g. , queue). Finally, we will discuss big-omega/big-theta notations and discuss lower bounds on the complexity classes of problems (not functions). We will revisit this topic later in the quarter to prove a non-trivial (and interesting) lower bound on sorting. In this section we will learn how to combine complexity class information about simple operations into complexity information about complex operations (composed from simple operations).