Time complexity, O, and W is a module of CS50 AP. It is recommended that teachers present this module as part of Unit 3.

Module Overview

The subject of computational complexity (also known as time complexity and/or space complexity) is one of the most math-heavy topics we discuss in CS50 AP, but also perhaps one of the most fundamentally important in the real-world. As we begin to write programs that process larger and larger sets of data, analyzing those data sets systematically, it becomes increasingly important to understand exactly what effect those algorithms have in terms of taxing our computers. How much time do they take to process? How much RAM do they consume? In this module, we begin to discuss the way in which computer scientists measure this, in particular considering the theoretical worst-case (O) and best-case (W) scenarios when running programs.

Video Resources

Written Resources

  • The canonical set of CS50 lecture notes for the time complexity, O, and W module is available here, here, and here.

Editable Slides

Download our editable PowerPoint slides. Please do not change or modify the first slide (containing the copyright notice).

Teaching Tips from CS50 AP Teachers

If you have tips that you've picked up from teaching this module to your students, please share them in this space!

In-Class Demonstration Ideas

If you haven't already watched this video comparing sorting algorithms side-by-side, it's worth a watch. Now that students possess the vocabulary to understand the theoretical runtime of some basic sorts, it may have more impact.

Thought Questions

  • In what ways can we measure the resources that our programs consume?
  • Is it always better to choose an algorithm that runs in O(n) over one that runs in O(n²)? Why or why not?
  • Why do you think that we analyze algorithms from a theoretical standpoint using asymptotic notation, instead of just counting runtime in seconds or the like?
    • In what ways does this adherence to asymptotic notation (disregarding constants and lower order terms) hinder our ability to speak about algorithms in the real world?
  • How might we use time complexity analysis to our benefit as programmers before we even write any code?

Recommended Resources External to CS50

Mapping to AP CSP Curriculum Framework

  • LO 4.2.1 -- Explain the difference between algorithms that run in a reasonable time and those that do not run in a reasonable time.
  • LO 4.2.4 -- Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity.

Mapping to CSTA K-12 Computer Science Standards

Not yet available