Introduction to computational complexity for non-ICT specialists
Introduction to computational complexity for non-ICT specialists
This lecture focuses on computational complexity which lies at the heart of computer science thinking. In short, it is a way to quickly gauge an approximation to the computational resource required to perform a task. Methods to analyse a computer program and to perform the approximation are presented. Speaker: David Lester.
Topics covered in this lesson
- Introduction to the 'while' programming language
- Cost analysis of a computation: average-case and worst-case scenarios
- Order of growth - the relationship between the size of the input and the run-time of the algorithm
- Dominant functions
- Upper and lower bounds of algorithm execution time
- Big-Oh, big-Omega notation
- Example: computational cost of sorting algorithms
Documents
Lecture Slides
(304.4 KB)
External Links