Skip to main content
Get your brand new Wikispaces Classroom now
and do "back to school" in style.
Pages and Files
CS50 AP Curriculum
Archived CS50 AP Updates
CS50 AP Educator Blogroll
Add "All Pages"
Big O notation
Time complexity, O, and
is a module of CS50 AP. It is recommended that teachers present this module as part of
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 (
) scenarios when running programs.
Download links (MP4)
(Time complexity, 5:09 to 23:26)
The canonical set of CS50 lecture notes for the
time complexity, O, and
module is available
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.
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
we even write any code?
Recommended Resources External to CS50
Doug's video on time complexity (from CS50 2015 and what will become eventually part of CS50 AP 1617)
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
help on how to format text
Turn off "Getting Started"