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.
© 2015 Joao Meidanis