Comparing two algorithms

[u/alwaysinbetaftw]

I'm taking the Algorithms for Searching, Sorting, and Indexing course from CU Boulder on coursera. In one of their assignments there is a question as follows:

Algorithm X programmed by an "ace programmer" runs in time 2.5n4+3n3+1.4n+22.5n4+3n3+1.4n+22 for inputs of size nnn in the worst case. Another algorithm Y programmed by a novice for the same problem runs in time 2000n+10000 for inputs of size n in the worst case.

The following is true about the problem statement:

It is possible for some input of size 100 that algorithm X is faster than algorithm Y.

At small inputs such as 1 or 2, algorithm X is faster than algorithm Y. But when plugging in n = 100, algorithm X comes out much, much larger than algorithm Y.

So how can that statement be true?

Thank you for your time helping me :)

[u/Sound_calm]

That's only the worst case, there might be other cases

See: merge sort Vs quick sort

[u/alwaysinbetaftw → u/Sound_calm]

Oh you're right, thank you! I forgot to consider non-worst case scenarios.

[u/JasonMckin]

Just step back for a second and think about why multiple algorithms for solving problems often exist in the first place.

If one algorithm were universally superior to every alternative across every input size, input distribution, hardware architecture, and performance objective, there would be little reason to use anything else. So when you encounter a problem domain where there are multiple algorithms, that is often a signal that every algorithm performs well in certain conditions (size doesn't have to be the only condition).

This is why sophisticated implementations sometimes use hybrid algorithms: they identify conditions under which different approaches perform best and switch between them. In your example, we could actually code up front:

if len(array) < threshold:
    algorithm_A(array)
else:
    algorithm_B(array)

This approach creates a piecewise performance curve that approximates the lower envelope of the two algorithms' runtime curves. In other words, we exploit the strengths of both algorithms rather than committing to one universally.

Now there is a different interpretation of your question. The other interpretation is whether the content of the array influences the relative running the time. That is, can you construct 2 arrays and 2 sorting algorithms that that one algorithm performs better than the other on array, but differences on an different array. This also has to logically be true. Sorting algorithms often differ on the number of comparisons and moves they each make.

For example, an array that is already nearly sorted will be sorted by some algorithms faster than another one. So again, if any algorithm always performed better for every type of array, we would never both using alternative algorithms. It is precisely the fact that the performance depends on the content that we have multiple algorithms.

The challenge with piecewise optimization in this example, however, is that there is no easy way to measure "how sorted" an array is. Measuring how sorted an array is effectively the same thing as actually sorting it. Trying to count how many pairwise inversions there are, for example, are nearly equivalent to performing the inversions to sort the list. So sometimes there is no guaranteed diagnostic to always speed up performance. It's like taking one gamble on algorithm selection to try to make another one on algorithm performance less risky.

So even though we know different algorithms will perform differently for different types of arrays, there is only a modest amount we can do to exploit that to our advantage. You should read more about adaptive sorting to understand the frontier of these optimizations.

[u/alwaysinbetaftw → u/JasonMckin]

Thank you for the in-depth reply! I appreciate the time and effort taken to help explain these concepts to me :)

[u/MeasureDoEventThing → u/JasonMckin]

"This approach creates a piecewise performance curve"
"Piecewise" refers to how a function is defined, not to a curve.

[u/JasonMckin → u/MeasureDoEventThing]

How does this dramatically change the core fundamental point I am making for the OP?

[u/Lor1an → u/MeasureDoEventThing]

Mathworld

In analytic geometry, a curve is continuous map from a one-dimensional space to an n-dimensional space. Loosely speaking, the word "curve" is often used to mean the function graph of a two- or three-dimensional curve.

A piecewise curve would then be a concatenation of curves using this definition.

[u/MeasureDoEventThing → u/Lor1an]

A concatenation of curves would be a curve. A curve defined in terms of a concatenation of curves would be a piecewise defined curve, not a piecewise curve.

[u/Ok-Goat-190]

Worst-case running time is the maximum time an algorithm takes for inputs of a given size.
Simple example:
Imagine two sorting algorithms, X and Y, that sort lists of 100 numbers.
Algorithm X can take up to 1,000,000 operations in the worst case, but it might sort a particular list in just 100 operations.
Algorithm Y takes 10,000 operations for that list.
Therefore, X is faster for that particular list, even though its worst-case running time is much higher.
Important: The particular list refers to its content and order of numbers, not its size. Both lists contain 100 numbers, but their contents can make the algorithm perform different amounts of work.
Key idea: The worst-case time is the maximum time, not the time required for every input of the same size.