6.2. Worst Case and Average Case Analysis

So, the first thing is the input size. So, remember that the running time of an algorithm necessarily depend on the size of the input. So, we want to write the running time as some function t of n. And the main thing to remember is that not all inputs of size n will give the same running time. So, there is going to be a notion of worst case estimate which you will need to explain and justify.

In this chunk, the discussion begins with the fundamental concept of input size in algorithms. The input size, denoted as 'n', plays a crucial role in determining how long an algorithm takes to run. It is essential to note that even inputs of the same size (n) can yield different running times, thus introducing the concept of a 'worst case' scenario, which is when an algorithm takes the longest to complete for a particular input size.

Think of input size like the number of guests at a dinner party. If you have 10 guests, the time it takes to serve them can vary: some might take longer to serve than others, resulting in different serving times even though the number of guests is the same.

Before we do this let us look at the notion of input size itself - how do we determine the input size for a given problem? So, the input size more or less represents the amount of space it takes to write down the distribution of the problem or becomes a natural parameter of the problem...

This chunk explains how to determine the input size for various problems. The input size can represent the number of items to be processed. For instance, when sorting arrays, the number of elements in the array is the input size. Similarly, in graph-related problems like airline route maps, both the number of cities and flights affect the input size. Understanding the context of a problem helps define its input size.

Imagine a library where the number of books represents the input size. If there are 100 books, that’s your input size. The effort and time needed to sort or organize these books will depend on how many books there are, just like an algorithm's performance depends on its input size.

Now, there is an important class of problems where we have to be a little bit careful about how we talk about input size, and these are problems involving numbers...

In arithmetic problems, the input size is not simply the value of the number but rather the number of digits in that number. The chunk discusses how when dealing with larger numbers, the number of digits (which relates to logarithms) ultimately influences the complexity of operations like addition and multiplication. For example, checking if a number is prime requires consideration of the number of digits rather than just its size.

Consider writing a check. It doesn't matter whether you write the amount as $100 or$1,000,000; what matters more is how many digits you need to write. Each digit represents a step in processing the number, similar to how an algorithm processes input based on the number of digits rather than their total value.

Now, the other thing, we mentioned this that we are going to ignore constants...

This chunk discusses the rationale behind ignoring constants when analyzing the efficiency of algorithms. If certain operations take multiple steps (like swapping values using temporary variables), treating them as a single operation simplifies analysis. By focusing on the general order of growth (like n, n^2), we can efficiently compare different algorithms without getting bogged down by minor operational details.

Think of it like packing for a trip. It doesn't matter if you take one or three bottles of shampoo; what matters is that you need a bag big enough for your toiletries. Similarly, in algorithm analysis, we focus on the overall size needed rather than the exact number of steps taken.

So, let us come back to this notion of worst case...

This chunk introduces the concept of 'worst case' performance in algorithms, which reflects the maximum time an algorithm could take relative to the input size. Using a simple algorithm that searches for a value in an unsorted array, it explains that the worst-case scenario occurs when the value is either at the end of the array or not present at all. This highlights the need to understand the algorithm's logic to determine what might constitute a worst-case scenario.

Imagine you're searching for a book in a disorganized library. The worst case would be if you check every single shelf and still don’t find it—or when the book is located on the very last shelf. This scenario embodies the worst case of your search.

Now, we could look at a different measure, right. So, supposing we do not look at the worst case, we say, look at the average case...

Here, the chunk discusses the average case analysis, which considers how an algorithm performs relative to typical inputs rather than only the worst-case scenario. However, calculating average case performance can be mathematically and practically difficult, especially when it comes to estimating the likelihood and distribution of different inputs, which makes it less feasible than worst case analysis.

Think about ordering food at a restaurant. The worst case might be waiting a long time for your food, but the average case could be how long most diners typically wait. However, if you don’t know how restaurant operations function and which meals are typically delayed, figuring out the average wait can be tricky.

To summarize, we look at worst case even though it could be unrealistic because the average case is hard if not impossible to compute...

In conclusion, while average case analysis might seem more intuitive and useful in certain scenarios, the practical challenges make worst case analysis a safer bet in algorithm design. By providing upper bounds on performance, worst case analysis ensures that we have a reliable expectation of how an algorithm will fare under challenging circumstances, allowing for better predictive capacity and informed decision-making in algorithm selection.

Consider studying for an exam. You prepare for the worst-case scenario where you get the most challenging questions (worst case analysis), rather than assuming an average set of questions will appear. This way, you ensure you’re adequately prepared for any situation you might encounter.

--