We will also write some small algorithms in the next chapters. This section shows how the performance of an algorithm can be estimated. During such analysis, it is often assumed that only a large input gives performance problems. The analysis will show how the running time scales when the input scales.
The next section requires some knowledge of basic mathematics. However, this section is not foreknowledge for the next chapters. If you do not understand a piece of this section, you can still follow the rest of the book.
For instance, if you want to find the index of an element in a list, you can use a for loop:
function indexOf(list: number[], item: number) { for (let i = 0; i < list.length; i++) { if (list[i] === item) return i; } return -1; }
This function
loops over all elements of the array. If the array has size n
, then the body of the loop will be evaluated n
times. We do not know how long the body of...