Description

for integer k
(d) If p(x) is any kth degree polynomial with a positive leading coefficient, then p(n) is O(nk).
2. Which function grows faster?
(a) nlogn; (logn)n
(b) lognk; (logn)k (c) nlogloglogn; (logn)!
(d) nn; n!.
3. If f1(n) is O(g1(n)) and f2(n) is O(g2(n)) where f1 and f2 are positive functions of n, show that the function f1(n) + f2(n) is O(max(g1(n),g2(n))).
4. Prove or disprove: Any positive
5. Prove or disprove: 3n is O(2n).