Asymptotic Notation
1.

Let f, t: N→R ≥ 0, and t (n) ∈O (f (n)) iff t(n)≤ c.f (n) where cis positive real constant and n≥ no, then no is ___________
A.  Upper bound B.  Lower bound C.  Duality value D.  Threshold value E.  Maximum value.
2.

The asymptotic notation for defining the average time complexity is
A.  Equivalence B.  Symmetric C.  Reflexive D.  Both (c) and (d) above.
3.

If f,t: N→ R+, then t (n) ∈ Ω (f (n)), iff f(n) ∈ O (t (n)) is known as
A.  Limit rule B.  Rule of inference C.  Duality rule D.  Rule of consequences
4.

The mathematical definition for Omega can be defined as, provided f,g:N→R+ and c is a positive constant and n > n0,
A.  f(n) ≥ c. g(n) n B.  f(n) = c. g(n) n C.  f(n) ≥ c + g(n) n D.  f(n) = c + g(n) n
5.

The θ notation is
A.  Symmetric B.  Reflexive C.  Transitive D.  (a), (b) and (c) above.
6. In analysis of algorithm, approximate relationship between the size of the job and the amount of work required to do it is expressed by using
A.  Order of magnitude or Big – O B.  Central tendency C.  Differential equation D.  Polynomial equation
7. Worst case efficiency of which search is O(n)?
A.  Sequential search B.  Binary search C.  Indexed search D.  Hashing
8. Which of the following formulas in Omega notation best represent the expression n²+35n+6?
A.  Ω (n³) B.  Ω (n²) C.  Ω (n) D.  Ω (35)
9. What term is used to describe an O(n) algorithm?
A.  Constant B.  Non Polynomial Deterministic C.  Logarithmic D.  Linear
10. Express the formula (n – 2)*(n – 4) using θ notation:
A.  θ (n^2) B.  θ (8) C.  θ (log n) D.  θ (n)