試題詳解

22. Let f(n) and g(n) be asymptotically positive functions. T(n) is the time an algorithm takes for an input of size n. Which one of the following statement is not correct?
(A) For the two functions (n) and g(n), either (n)-O(g(n)) or (n)=Ω(g(n))
(B) 1g(n^c)=O(Ign) for constantc＞0
(C) n^c=O(aⁿ) for constants c＞0 and a＞1
(D) For any uniform cost RAM program T(n) =Ω(S(n), where S(n) is the space an algorithm uses for an input of size n
(E) max(f(n),g(n))=θ(f(n)+g(n))