6.1.3. Special Case: Input Size for Numbers

So, the first thing is the input size. So, remember that the running time of an algorithm necessarily depends 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 algorithm design, understanding input size is crucial since it directly affects running time. You can think of running time as a function of input size (denoted as 'n'). However, it's important to note that not every input of size 'n' will take the same amount of time to process. Therefore, for any given algorithm, we often look for the 'worst-case' running time, which represents the maximum time taken by the algorithm for any input of that size. This helps in estimating the algorithm's efficiency in a conservative manner.

Imagine you are baking cookies, and the time it takes depends on the size of the batch. If you make 10 cookies, it might take a certain amount of time, but making 100 cookies could take much longer due to the increased workload. Just like we want to know the maximum time it might take for a batch of cookies based on the number of cookies (input size), we also want to figure out the worst-case time for algorithms based on their input sizes.

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.

To determine the input size for a problem effectively, you need to consider how the input is structured. Input size essentially reflects the amount of space required to represent the problem. For example, in sorting arrays, the number of elements in the array is a natural measure of size. This is because the execution time of sorting algorithms primarily depends on how many items need to be rearranged. Similarly, in other contexts, the relevant measure of size might differ based on the nature of the problem being solved.

Think about packing items into a moving van. The input size in this case could be the number of boxes you need to fit in. If you have 10 boxes, it will take you less time and effort compared to if you have 100 boxes. Similar to how you determine what matters when loading the van, individuals analyze input size in algorithms based on what aspect of the input is most important for the performance of the solution.

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. Now, how should we think of the size of the input?

When dealing with problems that involve numbers, such as checking if a number is prime, we cannot simply use the numerical value itself to define input size. Instead, we need to consider the number of digits in the number. This is because arithmetic operations depend on digit count rather than the magnitude of the number itself. As the number increases, while its value grows significantly, the number of digits (and consequently, the input size) increases logarithmically. Thus, input size in numeric problems is best represented by the logarithm of the number.

Consider how we write phone numbers. A phone number like 12345 has 5 digits, while 987654321 has 9 digits. When dialing, we focus on how many digits we have to press rather than the numerical value of the number. This example highlights that in various contexts, the size of the input can be more meaningfully represented by the number of 'spaces' or digits rather than the actual number itself.

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 grows as n, n square, n cube, and so on.

In algorithm analysis, particularly when estimating an algorithm's efficiency, we often ignore constant factors. This is because we are primarily interested in how the runtime scales as the size of input grows. For instance, if an algorithm takes 3n steps and another takes n steps, as n becomes large, the difference in constants (like 3 vs. 1) becomes negligible in comparison to the growth rates of n, n^2, n^3, etc. Thus, we generalize algorithm performance using 'big O' notation focusing on the highest order term and ignoring constant factors.

Imagine a train going faster but still not far enough to make a significant difference in travel time compared to a slower train, but the faster one gets affected by track signals. When calculating travel times over long distances (large inputs), the crucial factor becomes the speed of the train (or the growth rate in algorithm terms) rather than minor issues like the number of stops (constant factors).

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.

The worst-case analysis of an algorithm requires identifying which inputs will force the algorithm to operate for the longest time. For instance, if sorting an unsorted array where the desired number may not be present, the worst-case scenario occurs when the algorithm scans through all elements of the array to find that out. This worst-case runtime helps in understanding the upper limit of how long the algorithm might take to process inputs of size 'n', guiding developers in selecting appropriate algorithms for different scenarios.

Think of searching for a book in a library. If you look for a book that is not in the library, you will likely check every shelf before concluding that it is missing. The longest time it takes to search through every shelf represents the worst-case scenario for finding the book, which is an important consideration when planning how much time to allocate for 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, right.

While average-case analysis sounds appealing, it poses significant challenges because it requires an understanding of all possible inputs and their probabilities. In many real-world problems, computing the average case can be complex and sometimes intractable. This is particularly true for problems with large or infinite input spaces. As a result, implementing average-case analysis is often impractical, leading most to rely on worst-case analysis for practical algorithm evaluations.

Consider a weather prediction model. If you were to average out temperatures from all possible days, you would need extensive historical data to represent it accurately. Often, people focus on extreme weather events (like heatwaves) as these serve as stronger indicators of operational planning instead of simply calculating the average temperature, much like how programmers prioritize worst-case scenarios in algorithm analysis.

--