Skip to main content

Introduction to computational complexity for non-ICT specialists

Difficulty level

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
  1. Introduction to the 'while' programming language
  2. Cost analysis of a computation: average-case and worst-case scenarios
  3. Order of growth - the relationship between the size of the input and the run-time of the algorithm
  4. Dominant functions
  5. Upper and lower bounds of algorithm execution time
  6.  Big-Oh, big-Omega notation
  7. Example: computational cost of sorting algorithms
Lecture Slides (304.4 KB)