6.2.3. Summary of Worst Case vs. Average Case

The running time of an algorithm necessarily depends on the size of the input. We want to write the running time as some function t of n. 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.

This chunk emphasizes that the efficiency and running time of an algorithm are directly influenced by the size of its input. The term 'input size' refers to the quantity of that input, commonly denoted as 'n'. It's crucial to note that not every input of the same size will require the same amount of time for the algorithm to complete, leading to a special consideration for worst-case scenarios where the algorithm takes the maximum time.

Imagine you are trying to find your car keys in a bag with different items. If the bag is full (large input size), you may take longer to find the keys than if it's mostly empty. The worst-case scenario occurs when the keys are buried under a pile of clothes, taking a maximum amount of time to locate them.

The input size represents the amount of space it takes to write down the problem distribution or becomes a natural parameter of the problem. For instance, the size of an array is a natural notion of input size for a sorting problem.

Input size can vary depending on the nature of the problem being solved. In sorting, for example, the size is simply the number of elements in the array. In other types of problems, such as rearranging elements in containers, the number of items becomes significant.

Think of sorting books on a shelf: the number of books (the size of the input) determines how difficult the task is. More books mean more time spent sorting them properly. Similarly, if you were to load boxes into a truck, the number of boxes becomes your input size—one box is easy, but fifty boxes take much longer!

With problems involving numerical inputs, such as primality checking, the size of the input should be gauged by the number of digits instead of its magnitude. The number of digits is proportional to the logarithm of the number.

In cases where you're dealing with numbers, we need to think differently about what 'size' means. For example, the time it takes to check if a number is prime isn't about how large the number is, but how many digits it contains. The more digits, the more computations may be required, which relates to the logarithmic scale; therefore, the input size in these situations is best represented by its logarithm.

Consider doing math problems in school. When you add multi-digit numbers, you stack them up by their digits. The number of digits tells you how complex the addition might be; longer numbers lead to more columns of addition, similar to how the logarithm indicates complexity in algorithms.

We are going to ignore constants and look at functions in terms of orders of magnitude, such as n, n^2, n^3, etc. Including constants might complicate our analysis of efficiency.

When analyzing the running time of algorithms, we often simplify calculations by ignoring constant factors. This helps us focus on how the algorithm's time complexity scales as the input size grows. For example, we need to decide what operations to count as 'basic', and sometimes defining a swap as a single operation can make estimation clearer, even if it involves multiple behind-the-scenes actions.

Think of measuring how quickly you can bake cookies. While the exact time can vary (e.g., preheating the oven, mixing ingredients), you care mainly about the principle: if each batch takes 20 minutes, the important question is how many batches you can bake based on the number of cookies to make (input size). Understanding the overall process without getting bogged down in every detail helps you plan better.

To determine the worst case, we look for input that drives the algorithm to take the longest time. This is in contrast to the average case, which would require analyzing all possible inputs and their probabilities.

The worst-case analysis focuses on identifying the specific input scenario which elongates the algorithm's runtime. In contrast, the average case seeks to understand how algorithms perform over a variety of inputs. However, estimating average cases can be quite complex, especially when we cannot easily determine the likelihood of various inputs occurring. Therefore, worst-case analysis often serves as a more practical measure.

Imagine you're taking a standardized test. The worst-case scenario is when all the hardest questions appear; you'd need the maximum time to finish. But if you think about your average case—how well do you normally do?—that could be less clear because it depends on many different factors like your study habits and the mix of questions that show up on the test.

We focus on worst case because average case is hard to compute. If an algorithm has a good worst-case bound, it shows reliability. If not, we need to consider how often that worst case occurs in practical situations.

While worst-case analysis may present scenarios that seem unrealistic, it provides a crucial upper-bound estimate on the algorithm's performance. If we find that a certain algorithm has a poor worst-case bound, it prompts us to investigate further into the practical frequency of such cases and possible mitigating strategies.

Think about your personal budget: you might plan for the worst-case scenario where you face unexpected expenses. Even if this situation is rare, preparing for it helps you remain financially stable. Similarly, understanding an algorithm's worst-case performance prepares engineers for potential system failures, guiding them to improve efficiency.

--