Exercises marked with (*) require further reading/search beyond the suggested texts.
5. Say that you have two algorithms A1 and A2 for the same problem, whose input size is defined by parameter n. If A1 runs in time O(n/log n) and A2 runs in time O(n1/2), which one is the fastest asymptotically?
Answer:
A2 is is asymptotically faster. In the running time of A1, log n is very small compared to n, and therefore n/log n is almost the same as n. On the other hand, the running time of A2 is the square root of n, which is significantly smaller than n.
© 2015 Joao Meidanis