1 John tells you that a certain algorithm runs in time On 3

1. John tells you that a certain algorithm runs in time O(n 3 + 200n), and Bill tells you that the same algorithm runs in time (n 3 ). Can both John and Bill be correct? Why?

2. John tells you that a certain algorithm runs in time (2n + 200n), and Bill tells you that the same algorithm runs in time (n 3 ). Assuming that both statements are correct, which one is more informative, i.e., gives you a better estimation of the running time? Why?

Solution

1. Yes, both can be correct. This is because an algorithm running time can be theta(n^3). In that case, both omega(n^2) and O(n^3) are plausible.

2. Assumung that both are correct, omega(n^3) gives better estimation of running time. Since omega(1) can also be correct, highest value of omega notation is always preferred. Hence, for larger value of n, omega(n^3) will give better estimation