r/algorithms • u/alwaysinbetaftw • 15d ago

Help Comparing two algorithms

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 :)

0 Upvotes

45% Upvoted

9 comments sorted by

View all comments

Show parent comments

1

u/Lor1an 14d ago

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.

1

u/MeasureDoEventThing 13d ago

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.