On Tuesday, 26 January 2021 at 23:57:43 UTC, methonash wrote:
clip
That nested loop is an O(n^2) algorithm. Meaning it will slow
down *very* quickly as the size of the array n increases. You
might want to think about how to improve this algorithm.
Nice observation, and yes, this would typically be an O(n^2)
approach.
However, due to subsetting the input dataset to unique strings
and then sorting in descending length, one might notice that
the inner foreach loop does not iterate over all of n, only on
the iterator value i+1 through the end of the array.
Thus, I believe this would then become approximately O(n^2/2).
More precisely, it should be O( ( n^2 + n ) / 2 ).
But that is still O(n^2), you've only changed the constant.
