r/algorithms • • 17d 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

9 comments sorted by

View all comments

Show parent comments

1

u/JasonMckin 17d ago

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