6.2.2. Understanding 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.

In algorithm analysis, one crucial factor to consider is the input size. The input size refers to how much data the algorithm has to process, which is denoted as 'n'. When we analyze an algorithm, we express its running time as a function of n, noted as t(n). It is essential to understand that different inputs of the same size can result in varying running times due to their specific characteristics.

Consider a restaurant where the chef prepares meals based on ingredient lists (input sizes). If the chef has ingredients for 10 different dishes, the time taken to prepare each dish might vary due to complexity, even though there are the same number of ingredients.

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, for instance, when we are sorting arrays what really matters is how many objects there are to solve, so we have to move them around and rearrange them. So, the size of an array is quite a natural notion of input size for a sorting problem.

Determining the input size can vary based on the problem type. For example, in sorting algorithms, the number of elements in an array directly influences performance. Similarly, if we analyze a problem involving finding optimal loads for containers, the number of items becomes the primary input size. In graph-related problems, both the number of nodes (cities) and edges (flights) contribute to the input size.

Think of a bookshelf. If you're trying to arrange books (sorting), the number of books directly relates to how complex the task will be. More books mean a longer time to organize them compared to fewer books.

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. Suppose we were to write an algorithm for primality checking whether the given number is prime.

In numeric problems, like checking if a number is prime, the size of the input must be measured differently. While a number may be larger in magnitude, the effective size is its number of digits. For example, 50003 is not 10 times larger than 5003 in operational terms; instead, we should focus on how many digits these numbers contain, which relates to logarithmic scale. Thus, we often consider log(n) as the input size for these problems.

When typing a phone number, it doesn't matter how large the number is regarding its value; what matters is how many digits you have to type. Less complexity with fewer digits often translates to easier calculations.

Now, the other thing, we mentioned this that we are going to ignore constants. We are going to look at these functions in terms of orders or magnitude, thus the function grow as n, n square, n cube, and so on.

In algorithm analysis, we often simplify our calculations by ignoring constants because they don't significantly impact the overall growth of a function as the input size increases. By focusing on the order of growth (like n, n², n³), we can better understand which algorithms will be more efficient for larger inputs.

Imagine running a race. Whether you take 5 steps or 6 steps to the starting line might not matter much compared to the distance of the race itself (the main factor). In the grand scheme of the race's total length, those few extra steps are negligible.

So, let us come back to this notion of worst case. So, as we said we are really looking at all inputs of size n; and, among these inputs which inputs drive the algorithm to take the maximum amount of time.

When analyzing algorithms, determining the worst-case scenario involves considering all inputs of a given size and identifying which specific input configuration causes the algorithm to take the most time to process. This provides insights into the algorithm's efficiency in the least favorable conditions.

Imagine you're looking for your keys in a messy room (worst case), where you have to check every possible place. Alternatively, if you know where they usually are, you quickly find them (average case), showing that your usual scenarios might be easier but not always.

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, right. ... In practice, it is very hard to do this because we cannot really quantify this space of possible inputs and assign them with meaningful probabilities.

Average case analysis calculates the expected performance across all possible inputs. However, it can be challenging to estimate and define what an average input looks like, particularly when the inputs' probabilities may not be easily quantifiable. This complexity often limits our ability to perform average-case analysis effectively.

Think about predicting traffic on a road. Sometimes it's congested, sometimes it’s easy to navigate. Determining the average time taken during various conditions can be tough because different factors (like accidents or roadworks) affect overall flow unpredictably.

To summarize, we look at worst case even though it could be unrealistic because the average case is hard if not impossible to compute. ... Thus, even in the worst case if algorithm performs efficiently then we have got a useful piece of information about the algorithm.

In conclusion, while worst-case analysis can be unrealistic, it provides a practical way to assess algorithms since average-case scenarios are often challenging to compute. Understanding an algorithm's worst-case behavior helps identify its efficiency limits and highlights potential issues to address.

Like a stormy weather forecast predicting the worst case of rain, this gives you a good idea of the limitations you might encounter. By preparing for the worst, you are more likely to handle unexpected situations effectively.

--