MO640 - Exercises - Informatics Concepts, Setubal and Meidanis 1997 - chapter 2

Exercises marked with (*) require further reading/search beyond the suggested texts.

4. Explain how an O(n2) algorithm can be faster than an O(n) algorithm for small values of n.

Answer:

When analyzing algorithms, we ignore some constants. But if we check the actual functions that represent the worst-case running times of algorithms, we may find values of n for which an O(n^2) algorithm ends up being faster than an O(n) algorithm.

For example, say Algorithm A takes time n2 and Algorithm B takes time 100*n on inputs of size n. Although B is O(n) and A is O(n2), we see that n2 < 100*n when n < 10.


MO640 Home

© 2015 Joao Meidanis