Tuesday, August 22, 2006

"Big O" notation and Complexity Analysis

Topics

• Algorithm efficiency as classified by the Big O, Big Omega, and Big Theta notation
• Practical examples of the most common Big O functions
• Best case, average, and worse case

Readings

Chapter 2, all except Section 2.9 and 2.10.  You should try to understand the mathematical definitions and formulas of Sections 2.2, 2.3, and 2.4, but you will not have to prove or derive them.  Also, make sure you understand the concepts of Section 2.7, but you may skim through the math at the end of that section.   The examples in Section 2.7 illustrated what we will be talking about during the rest of the course.   We will only have two or three classes during the semester that focus on math.  You will not be tested on any math in this course beyond a general understanding of the concepts and their practical importance.  There will be no mathematical problem solving, derivations, or proofs.  If you plan on going into a mathematically based, or engineering based, Computer Science program, such as UI Urbana-Champaign, you will have a lot of math similar to what is in this text.  If you plan on going into a more career oriented or Business based Computer Science program, such as UI-Springfield or Illinois State, you will have some, but not nearly as much required math.