6.1. Input Size and Running Time

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.

The input size refers to the amount of data the algorithm has to work with, which directly affects its running time. We can represent this relationship as a function of 'n', where 'n' denotes the size of the input. However, it’s important to note that different inputs of the same size may have varying effects on the running time of the algorithm.

Consider a postal delivery service that has to sort and deliver packages. The time it takes to sort depends on not just the number of packages, but also factors like package size and weight. Similarly, in algorithms, the complexity can change based on different factors, even if two datasets are of the same size.

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.

Input size can often be measured in terms of relevant factors associated with a problem. For example, in sorting arrays, the number of objects (or the length of the array) is a natural input size. In graph-related problems, the number of nodes and edges influences the input size. Understanding what constitutes the input size is crucial for analyzing an algorithm’s efficiency.

Imagine packing items into boxes. The number of items (input size) directly relates to how long it will take to pack them, similar to how an algorithm processes data. If each item needs special care or packing steps, that also affects the time taken, just as different array types influence algorithm performance.

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 numerical problems, such as determining if a number is prime, the size of the input should not be viewed just in terms of the numerical value itself but rather the number of digits in that number. For instance, the number 50003 has more digits than 5003, which takes a different amount of computational resources.

Think about using a calculator for large multiplications. The time taken is less about the size of the numbers (like 5003 vs 50003) and more about how many digits you are working with. Just like counting change, it’s easier to handle smaller quantities than larger sums, complicating the processing time.

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 deal with large inputs, and we care more about how the running time scales rather than the exact numbers involved. By focusing on the order of growth (like n, n squared, etc.), we can simplify comparisons between different algorithms. Ignoring constants helps clarify which algorithm will be more efficient for larger datasets.

Consider running a marathon: it doesn’t matter exactly how much water you carry (constant) as long as you know that more water means more weight, which can slow you down (order of growth). If two runners carry the same amount of water, we can focus on their speeds instead.

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 involves looking at the scenario that would make the algorithm take the longest time to execute. For an unsorted array, finding an element requires checking each entry until you find the target or exhaust the list. This consideration is crucial for understanding the performance limits of an algorithm.

Imagine you’re searching for a lost item in a cluttered room: the longest time you could take is if the item is hidden at the very back or not there at all. This reflects worst-case analysis in algorithms where you want to ensure you’re prepared for the longest 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.

Average case complexity considers the running time across a set of potential inputs that can be encountered under typical conditions. However, calculating this can be complex because you need to estimate probabilities concerning various input scenarios, which is often challenging. Thus, average-case analysis is not always practical.

Think of it like predicting how long your cooking will take. If you usually cook different dishes, averaging the time it takes for each meal gives you an estimation. But unpredictables like ingredient availability can complicate that average, much like the diverse inputs algorithms face.

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 worst-case analysis can offer a safe estimate of the limits of an algorithm's efficiency, average-case analysis is often more desirable as it reflects expected performance. However, calculating the average case can be challenging due to the complexities in estimating input probabilities, making worst-case scenarios practical judges of performance.

It’s like being a driver: understanding the worst traffic conditions provides crucial insights for planning a trip (worst case), but actual journey times can fluctuate. Thus, while the worst-case scenario impacts decisions, average journey times give daily insights.

--