6.2.1. Definition of Worst Case

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.

Input size refers to the amount of data that an algorithm needs to process. For example, in a sorting algorithm, the input size could be the number of elements in the array that need rearranging. When analyzing an algorithm’s efficiency, we express the running time as a function of the input size, typically denoted as t(n). It is crucial to note that not all inputs of the same size will produce identical running times. This leads us to the consideration of the worst-case scenario, which helps us understand how the algorithm performs under the least favorable conditions.

Think of planning a dinner for a large group. The number of guests (input size) determines how much food you need to prepare (running time). If you have one large guest who eats twice as much as the others, while overall the group is big, it might take much longer to prepare than if all guests ate similar portions. Thus, the worst-case scenario helps to visualize the maximum effort needed.

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. On the other hand, if you had trying to do something like rearranging elements or take say we have some items which we need to load into a container and we are looking for optimum subset load in terms of weight or volume then the number of objects would be a natural input parameter... if we have a graph then both the number of nodes or vertices and the number of edges will determine the input size.

In computational problems, the identification of input size can vary based on the context. For sorting arrays, the input size is the number of elements in the array. In another scenario, like loading items into a container, the number of items becomes the primary input parameter. In graph-based problems, both the number of nodes (vertices) and the connections between them (edges) are important as they influence the complexity of algorithms that operate on these graphs.

Imagine organizing a shelf full of books. The number of books represents the input size for an organization algorithm. If you had two shelves—one with 10 books and another with 100—arranging the books on the second shelf will take significantly longer due to the increased number of items, similar to the way an algorithm's efficiency is impacted by 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... the number of digits determines how many columns we have to add.

For problems involving numerical inputs, the way we measure input size may differ. Instead of considering the numerical value itself, which could be misleading, we consider the number of digits in the number, because this directly correlates to the complexity of algorithms performing operations on these numbers. For instance, if you think of the number 50003, you focus on its digits ('5', '0', '0', '0', '3'), and the time taken to process this will depend more on how many digits it has rather than just its magnitude.

Consider dialing a phone number. The longer the number, the more time it takes to enter it properly. If you need to remember a number with 7 digits versus a 5-digit one, your brain might find the longer one a tad more complicated, similar to how algorithms handle larger digit-containing numbers differently.

Now, the other thing, we mentioned this that we are going to ignore constants... that is in other motivation for only looking at orders of magnitude.

When analyzing algorithms, we often choose to ignore constant factors because they do not significantly affect the growing competition as input size increases. For example, whether an operation takes 3 steps versus 1 step becomes less relevant when considering the general growth of the algorithm’s running time as input size multiplies. This simplification allows us to focus on the most critical aspects of algorithm efficiency.

Imagine you're baking cookies. Whether you bake 10 cookies at a time or 12 doesn't significantly change your overall baking time if you're using the same oven. Focusing solely on the size of the batch rather than minor differences makes it easier to gauge when you'll be ready instead of getting lost in the little inconsistencies.

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

The worst-case scenario of an algorithm is defined by the input that makes it take the longest possible time to complete its task. For instance, if we look for an element in an unsorted array, the worst case is when the element is at the last index or not present at all. In such instances, the algorithm must check every element until it concludes, thereby maximizing its run time, which associates directly with the input size.

Consider trying to find a specific book in a disorganized library. If the book you're looking for is the last one on the shelf or even missing, you would need to check each book one by one until you reach the end, representing the worst-case scenario in terms of your time and effort.

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

While average-case analysis may seem appealing as it reflects normal conditions, it is often impractical due to the complexities involved in estimating probabilities of different inputs. Worst-case analysis, although it may not always reflect typical performance, provides a reliable upper bound on running times. Understanding the worst case can help in determining if an algorithm is usable in real-world applications and can lead to further investigation of specific problematic inputs.

Imagine a fire drill procedure where the worst-case scenario is a building filled with 100 people. Practicing for this worst-case scenario ensures preparedness and helps plan the safest and most efficient exit strategy. This is similar to examining algorithms under the worst conditions to be ready for any situation.

--