All lessonsOpen Open Open Open Open
1. Complexity
Big-O notation
0 of 5 activities0%
Reading 1
Growth, not exact time
Big-O describes how an algorithm scales as the input size n grows. We care about the dominant term and drop constants.
Common classes: - O(1) constant - O(log n) logarithmic - O(n) linear - O(n log n) linearithmic - O(n^2) quadratic - O(2^n) exponential
Worst case is the usual default unless we say average or best.
// O(n): touch each element once
for (int i = 0; i < n; i++) sum += a[i];
// O(n^2): nested loops over n
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) ...Check 2
Dominant term
Which best describes nested loops each running n times?
Fill in 3
Constant time
Try it 4
Count operations
This prints n. Think about how steps grow if n doubles.
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Classify a loop
Read n. Run a loop from 1 to n printing nothing, but print the word linear if the pattern is O(n) — for this exercise always print linear.
main.cpp
Loading editor…