7 Algorithm analysis, part 3: Advanced theory

In this chapter, we move beyond basic runtime analysis to develop a richer understanding of algorithm performance. We consider not only execution time, but also memory usage. By examining these aspects, we gain deeper insights into the efficiency and practicality of advanced algorithms.

We start by examining space bounds and memory complexity, which are important when working with large datasets or constrained hardware. Next, we introduce amortised analysis, a method for evaluating the average performance of sequences of operations, where infrequent costly steps are balanced by many inexpensive ones. We then delve into recurrence relations, which are key to analysing the complexity of recursive functions, and demonstrate several techniques for solving them. Finally, we address algorithms influenced by multiple input parameters, learning how to express and analyse their complexity.