Analysing Complexity

Analysing complexity is reading a function's cost from its code: how many times each line runs, and how much memory it adds, as its input grows. It matters because the class written beside a data structure operation is only useful if you can find it in your own code, where loops nest, functions call themselves and one built-in call can hide a whole loop. The topic starts with a four-step count on a function that sums a list, applies it to loops in sequence, nested loops and a counter that halves, and corrects the habit of calling every nested loop O(n²). It then counts extra space, including the call stack, gives two independent inputs a variable each, and finds the linear work inside list searches, slices and string building. How a recursive call works belongs to Recursion, and amortised cost to Arrays and Strings.