Introduction to Computational Complexity for Non-ICT Specialists
Introduction to Computational Complexity for Non-ICT Specialists
This lecture focuses on computational complexity, a concept 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.
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
