Answer the following questions. All running times refer to the worst-case analysis. 1. John came up...

Transcribed Image Text:

Answer the following questions. All running times refer to the worst-case analysis. 1. John came up with an algorithm for some problem that runs in time (n² log(n)), and Bill came up with an algorithm for the same problem that runs in time o(n² log(n)). Based on this information, which one would you choose? Why? John tells you that a certain algorithm runs in time O(na +200n), and Bill tells you that the same algorithm runs in time n(n³). Can both John and Bill be correct? Why? 3. John tells you that a certain algorithm runs in time n(n² + 200n), and Bill tells you that the same algorithm runs in time n(n). Assume that both statements are correct, which one is more informative, i.e., gives you a better estimation of the running time? Why? Answer the following questions. All running times refer to the worst-case analysis. 1. John came up with an algorithm for some problem that runs in time (n² log(n)), and Bill came up with an algorithm for the same problem that runs in time o(n² log(n)). Based on this information, which one would you choose? Why? John tells you that a certain algorithm runs in time O(na +200n), and Bill tells you that the same algorithm runs in time n(n³). Can both John and Bill be correct? Why? 3. John tells you that a certain algorithm runs in time n(n² + 200n), and Bill tells you that the same algorithm runs in time n(n). Assume that both statements are correct, which one is more informative, i.e., gives you a better estimation of the running time? Why?