Q1. If f(n) = 3n 2 + n 3 lg n, then f(n) is
a. O(n2)
b. O(n 3/2 )
c. O(n^3 lg n)
d. O(n 2 /3)

Q2. What is the asymptotic relationship between the functions: x^p and k^x? (Assuming that p ≥ 1 and k > 1 are constants:)
a. x^p is O(k^x )
b. k^x is O(x^p )
c. x is O(k)
d. Both b and c

Q3. For functions, nk and cn , what is the asymptotic relationship between these functions? Assume that k ≥ 1, and c ≥ 1 are constant.
a. n^k is O(cn)
b. n^k is Ω(cn)
c. nk is Θ(cn)
d. None of the above

Q4. If f(n) = 5 lg n + 2 lg n! + (n 2 + 1) lg n, what is the big-O notation for f(n)?
a. n
b. n^2
c. n lg n
d. n^2 lg n

Q5. What is the time complexity for the following piece of code?
sum = 0;
for (int i = 0; i < n; i++)
for (j = 1; j < n; j = j * 2)
sum += n;
a. O(n2)
b. O(n)
c. O(lg n)
d. O(n lg n)

Q6. If f(x) = (x^3 − 1) / (5x + 1) then f(x) is
a. O(x^2 )
b. O(x)
c. O(x^3 /5)
d. O(1)

Q7. The Big-O complexity of 1 + 2 + 3 + 4 ... + n is? (Assume we must add the numbers one at a time, rather than using Gauss's trick to get a closed form for the sum.)
a. O(n)
b. O(n 2 )
c. O(3n)
d. O(n 3 )

Q8. The Big-O complexity of 1 + 2 + 3 + 4 + ... + 100 is? (Assume we must add the numbers one at a time, rather than using Gauss's trick to get a closed form for the sum.)
a. O(1)
b. O(n)
c. O(n2)
d. O(3n)