CMPS 260: Data Structures
Introduction
Implementing an algorithm and getting it to work is important, but it is not the whole story. It is also important to assess how well the algorithm performs, especially when the input gets larger. For example, if you have an array with 10 elements it does not matter much which algorithm you use to sort them. But if you have an array with 1,000,000,000 elements the different algorithms will have quite different time usage characteristics. This is expressed using the big O notation and can be applied to both time and spaces. For example, quick sort is much faster than bubble sort because the former requires many fewer steps. We will also briefly look at the theory for NP completeness. We say an algorithm is efficient if it runs in polynomial time. All algorithms that can be solved in polynomial time in the worst case belong to P. All algorithms for which the solution can be checked in polynomial time is in NP. P is a subset of NP but it is currently unknown whether P=NP and this is one of the major unsolved computer science problems. NP complete problems are the hardest problems in NP.
Module Objectives
- Explain big O notation
- Assess the complexity of algorithms
- Explain NP completeness
Learning Resources
- Module 13 Readings: Chapter 12
- Module 13 Slides: Chapter 12
Learning Activities
- Module 13 Assignment
For Further Study
- Read more about big O notation on Wikipedia
- Read more about algorithm complexity on Wikipedia
- Read more about NP completeness on Wikipedia