Spend extra time teaching Big O in intro classes that use Python because the underlying implementation of Python lists is a mystery to students that leads students to believe many operations are constant, O(1), that are not.
- This confusion about Big O notation may inhibit deeper understanding of Big O, particularly when it comes to comparing implementations of functions, data structures, etc. (e.g., operations on linked lists vs. Python lists).
- Students can get really confused about asymptotic analysis when Python’s their first programming language.
- Because Python removes interactions with the underlying structures and algorithms that run Python lists, it is more difficult to motivate run time of Python list operations.
- This issue provides you, the teacher, with an opportunity to discuss the following topics which serve as a nice preview for the CS2 course:
- how Python implements lists at a high level.
- how Python provides a high-level list abstraction that hides the implementation details from the programmer.