Skip to main content

Introduction to Computational Complexity for Non-ICT Specialists

Difficulty level
Beginner
Speaker
Type
Duration
27:33

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)