Asymptotic Notation Questions

MCQ bookmark_border

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.

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

2.

The asymptotic notation for defining the average time complexity is

A

Equivalence

B

Symmetric

C

Reflexive

D

Both (c) and (d) above.

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

The θ notation is

A

Symmetric

B

Reflexive

C

Transitive

D

(a), (b) and (c) above.

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

Worst case efficiency of which search is O(n)?

A

Sequential search

B

Binary search

C

Indexed search

D

Hashing

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

Which of the following formulas in Omega notation best represent the expression n

A

Ω (n³)

B

Ω (n²)

C

Ω (n)

D

Ω (35)

Correct Answer: B

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

What term is used to describe an O(n) algorithm?

A

Constant

B

Non Polynomial Deterministic

C

Logarithmic

D

Linear

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

Express the formula (n – 2)*(n – 4) using θ notation:

A

θ (n^2)

B

θ (8)

C

θ (log n)

D

θ (n)

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion