6.1.1. Definition of Input Size

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 is a critical factor when measuring an algorithm's efficiency. The running time of any algorithm is influenced by the size of its input, denoted here as 'n'. It's important to note that different arrangements of the same number of inputs can lead to different running times. This variability leads to the concept of the 'worst case', which provides a way to evaluate the maximum time the algorithm might take based on specific inputs.

Consider a librarian who needs to find a specific book in a library. If the books are arranged in alphabetical order (a well-structured input), she can find the wanted book quickly. However, if the books are scattered everywhere (a disorganized input), it might take her much longer, highlighting that not all inputs yield the same processing time.

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.

The input size is fundamentally about the 'space' required to represent the problem. Depending on the specific problem type, input size can vary. For example, in sorting algorithms, the size of the array is a natural indicator of input size. In other problems, such as container optimization, the number of items to be loaded might be more relevant, showcasing that input size can vary widely based on the specific context of the problem being solved.

Think about packing for a trip. If you have to pack ten clothes, it takes less space and time compared to packing fifty clothes. Just like the amount of travel gear changes how quickly you can prepare, the 'size' of the input determines how efficiently the algorithm can function.

If we have a graph then both the number of nodes or vertices and the number of edges will determine the input size.

In graph-related problems, the input size is categorized by two main factors: the number of nodes (or vertices) and the number of edges connecting those nodes. Both these quantities play a significant role when analyzing the performance of algorithms that operate on graphs since more nodes and edges can lead to a more complex scenario requiring more time to analyze and compute.

Visualize a social network like Facebook or LinkedIn. Each person represents a node, and the friendship or connection between them is an edge. A network with a few friends (nodes and edges) is easy to navigate, while a vast network with thousands of connections becomes increasingly intricate and time-consuming to analyze.

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.

For numerical problems, defining input size can be ambiguous. When looking at numbers, rather than considering the number itself (like 5003 versus 50003), we focus on the number of digits it contains, as this impacts the computation. The number of digits, which corresponds to the logarithm of the number in a particular base (like base 10), gives us a more accurate measure of input size for algorithms dealing with numerical analysis.

Imagine you are multiplying two large numbers. It’s easier to do this with smaller numbers with only a few digits (like 1234) compared to much larger numbers (like 123456789). Just like you count fingers to count small groups of items, in mathematics, you count the digits to assess complexity.

So, we mentioned 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.

When analyzing algorithms, the focus is typically placed on the growth rates of their running times rather than on constant factors which may not meaningfully influence performance at a larger scale. For instance, increasing the number of operations by a constant factor (like 3) doesn’t change the overall complexity class; therefore, analysts look at broader trends like order of growth (O(n), O(n^2), etc.) rather than specific operation counts.

Think of baking cookies. Whether you bake two dozen or three dozen cookies, the overall baking time remains quite steady. Thus, instead of focusing on the exact number of cookies baked (the constant), we simply classify cookie-baking as taking a certain amount of time related to the baking process overall, noting it's more about the proportion than the specifics.

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.

Worst case analysis investigates the most time-consuming input that an algorithm can handle within a given size category, 'n'. Understanding which inputs push the algorithm to take the longest time is crucial, as this helps in identifying scenarios where the algorithm could potentially fail or perform poorly. It emphasizes the importance of analyzing the specific characteristics of the algorithms.

Consider a search party looking for a lost hiker. If the terrain is vast and difficult, the last few places they check could take longer, especially if the hiker isn’t where they expect. That hardest-to-find scenario exemplifies the worst-case scenario in their 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.

The average case analysis attempts to determine the expected running time across all possible inputs. However, accurately quantifying 'average' often proves difficult due to the necessity of knowing how likely different inputs are. In many contexts, the numerous variations and infinite possibilities complicate this estimation, making it less practical than worst-case analysis.

Think about predicting the average time it takes to find your keys. Some days you might find them quickly, while on others, they could take ages. With so many variables (where you usually put them, how distracted you are, etc.), forecasting an average 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 offers valuable insight about an algorithm’s general performance, the complexity of defining 'average' often makes it less feasible. Consequently, worst-case analysis becomes a preferred method, providing a reliable upper bound by assessing how a given input could negatively impact performance. Though it may not reflect typical scenarios, it offers a mathematically sound way of estimating an algorithm’s efficiency.

Like evaluating the maximum load capacity of a bridge, where you focus on the heaviest conceivable vehicle, worst case analysis gives you an assurance that even under extreme conditions, you know the bridge will hold up! It's about knowing its limits rather than daily traffic.

--