Chapter 1 of 8: Complexity classes review
Bell counts calls in subset generation, Fibonacci and bisection search to assign each a class.
Time complexity classes for Python code, from to exponential, follow from counting operations, loop iterations and recursive calls. In session 22 of MIT's introductory Python course, Bell reviews notation, then works constant, linear and polynomial cases built from single and nested loops. Recursive subset generation and Fibonacci show branching calls producing exponential growth. Bisection search on a sorted list runs in logarithmic time because each step halves the search space. The closing question weighs sorting before searching: one query favours a linear scan, while many queries justify the sort. Basic Python and the previous lecture's treatment of asymptotic notation are assumed.
Time complexity classes for Python code, from to exponential, follow from counting operations, loop iterations and recursive calls. In session 22 of MIT's introductory Python course, Bell reviews notation, then works constant, linear and polynomial cases built from single and nested loops. Recursive subset generation and Fibonacci show branching calls producing exponential growth. Bisection search on a sorted list runs in logarithmic time because each step halves the search space. The closing question weighs sorting before searching: one query favours a linear scan, while many queries justify the sort. Basic Python and the previous lecture's treatment of asymptotic notation are assumed.
This lecture
Lecture 22 of 25 of Introduction to Computer Science and Programming using Python.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in