1. For each function f(n) below, give an asymptotic upper bound using big-Oh notation. You should give the tightest bound possible (so giving O(2n

) for every question is unlikely to result

in many points). You must choose your answer from the following list. The list is not in any particular order and any item in the list could be the answer for 0, 1, or more than 1 question. O(n), O(n2 ), O(2n ), O(n1/2), O(n1/4), O(n3 ), O(n4 ), O(n5 ), O(n6 ), O(n7 ), O(n8 ), O(n9 ), O(log3

n), O(n2 log n), O(log8

n), O(log4

n), O(n log3

n), O(log2

n), O(log n), O(1), O(n3 log

n), O(nn ), O(n log log n), O(n log2

n), O(log log n), O(n log n) (2 points each)

(a) f(n) = (n log n) (n + n2 )

(b) f(n) = 100 (c) f(n) = 2 log log n + 9 log2 (n)

(d) f(n) = SQRT(n) + log n (e) f(n) = n3

(1 + 5n + n2 ) n5

(f) f(n) = log (3n2 )

(g) f(n) = 25 + 4n2

n2 log2 n n(log2 n) 2