Let P be a problem. The worst-case time complexity of P is . The worst-case time complexity of P is also . Let A be an algorithm that solves P. Which subset of the following statements are consistent with this information about the complexity of P?
Suppose that an algorithm A runs in worst-case time f(n) and that algorithm B runs in worst-case time g(n). For each of the following questions, answer either yes, no, or can't tell and explain why.
(a) Is A faster than B for all n greater than some if ?
(b) Is A faster than B for all n greater than some if ?
(c) Is A faster than B for all n greater than some if ?
(d) Is B faster than A for all n greater than some if ?
(e) Is B faster than A for all n greater than some if ?
(f) Is B faster than A for all n greater than some if ?
For each of these questions, briefly explain your answer.
(a) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on some inputs?
(b) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on all inputs?
(c) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on some inputs?
(d) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on all inputs?
(e) Is the function , where for even n and for odd n?
For each of the following, answer yes, no, or can't tell. Explain your reasoning!
(a) Is ?
(b) Is ?
(c) Is ?
(d) Is ?