This chapter covers two topics that are advanced: time complexity and recursion. They don’t really have anything to do with each other.
How fast is your program? That is the question that we try to answer by using time complexity. The second half of this chapter introduces a critical idea about measuring how long a program takes, beyond our previous criteria of being correct and easy to understand. Three different ways of measuring the length of a program are covered, including the number of lines, the time the program takes according to a watch, and an estimation-approach called the RAM Model of Computation. We only really scratch the surface of the idea of Time Complexity, but this lays the foundation for a lot of important concepts later on.
A substantial section of this chapter is dedicated to two specific problems: sorting and searching. These two problems have been seriously studied for many years in Computer Science, and are very well understood. Furthermore, they have interesting properties that make them very educational for those just starting off. Searching is a problem we have seen before, where we are trying to find an element in a list. Previously, we used an iterative search algorithm to check each element. However, in the worst case, that might require as many checks as there are elements in the list. A massive improvement can be found by using Binary Search, which repeatedly divides the search space in half, achieving logarithmic time complexity. In order to use Binary Search, however, the list must already be sorted. Sorting a list means putting the elements in order. There are many algorithms for sorting a list, although we will only look at a few of them. You can expect to revisit searching and sorting many more times in the future.
This is when a function calls itself.
This is when you nest references to instances inside of themselves, in a layered data structure.