Q1- f(n) = small-omega(g(n)) if and only if
(a) g(n) = small-oh(f(n))
(b) g(n) = small-omega(f(n))
(c) g(n) = Big-omega(f(n))
(d) g(n) = Big-Oh(f(n))
(d)
Q2- Which of the following is true?
(a) f(n) = Big-Omega(f(n))
(b) 25*f(n) = Big-Oh(f(n))
(c) f(n) = small-oh(f(n))
(d) O(f(n) + g(n)) = o(f(n) + g(n))
(a) and (b)
Q3- Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is
(a) O(1)
(b) O(logn)
(c) O(n)
(d) O(n2)
(d)
This is an array multiplier and each gate in circuit has a unit delay. The total delay of multiplier is n*n*unit delay, and unit delay is a constant time.
Q4- Using an algorithm, what is the time required to determine that the number n is prime?
(a) theta(n)
(b) theta(logn)
(c) theta(1)
(d) Can’t say
(d)