- Explain different runtimes using the following three methods to find and tell a friend the number of stairs of the Eiffel Tower:
- You can read a sign at the bottom of the tower that tells you the number of stairs.
- This represents O(1) time, constant runtime.
- Your friend walks up the tower with you as you count the stairs.
- This represents O(N) time where N is the number of stairs, linear runtime.
- Your friend stays at the bottom of the tower and each time you go up one more stair you come back down and tell them you climbed another stair.
- This represents O(N2) time, quadratic runtime.
- Ask students how the height of the tower affects runtime to start a discussion about how input size is important in algorithm development.
- What happens to the runtime of each method if the tower is much taller?
- What happens to the runtime of each method if the tower is much smaller?