Home » MCQs » Discrete Mathematics MCQs

Discrete Mathematics | Algorithms and Functions MCQs

Discrete Mathematics | Algorithms and Functions MCQs: This section contains multiple-choice questions and answers on Algorithms and Functions in Discrete Mathematics.
Submitted by Anushree Goswami, on July 17, 2022

1. Which of the following is/are a/the characteristic(s) of Algorithm?

1. Input
2. Output
3. Precision
4. All of the above

Answer: D) All of the above

Explanation:

The characteristics of Algorithm are input, output, precision, etc.

---

2. How many quantities are externally supplied in input?

1. Zero
2. Zero or more
3. One
4. Atleast one

Answer: B) Zero or more

Explanation:

Zero or more quantities are externally supplied in input.

---

3. How many quantities are produced in output?

1. One
2. Atleast One
3. Multiple
4. Zero

Answer: B) Atleast One

Explanation:

Atleast one quantity is produced in output.

---

4. In precision, each instruction is -?

1. Clear
2. Unambigous
3. Both A and B
4. None of the above

Answer: C) Both A and B

Explanation:

In precision, each instruction is clear and unambiguous.

---

5. Which of the following is not the characteristic of algorithm?

1. Feasibility
2. Flexibility
3. Generality
4. Infiniteness

Answer: D) Infiniteness

Explanation:

Infiniteness is not the characteristic of algorithm.

---

6. A ____ number of instructions must be executed for the algorithm to complete?

1. Multiple
2. Finite
3. Infinite
4. None

Answer: B) Finite

Explanation:

A finite number of instructions must be executed for the algorithm to complete.

---

7. Flexibility refers that -?

1. A change to the algorithm should also be possible without putting a great deal of effort into it.
2. A change to the algorithm should not be possible without putting a great deal of effort into it.
3. A change to the algorithm should also be possible putting a great deal of effort into it.
4. None of the above

Answer: A) A change to the algorithm should also be possible without putting a great deal of effort into it.

Explanation:

Flexibility refers that a change to the algorithm should also be possible without putting a great deal of effort into it.

---

8. In algorithm analysis, _____ estimates are derived to determine how long an algorithm will take to execute?

1. Time
2. Space
3. Both A and B
4. None of the above

Answer: C) Both A and B

Explanation:

In algorithm analysis, time and space estimates are derived to determine how long an algorithm will take to execute.

---

9. An algorithm's _____ is the estimation of how much time and space will be required to execute it?

1. Time complexity
2. Space complexity
3. Time and space complexity
4. Time or space complexity

Answer: C) Time and space complexity

Explanation:

An algorithm's time and space complexity is the estimation of how much time and space will be required to execute it.

---

10. A ____ of the input determines how long an algorithm will take to execute?

1. Value
2. Function
3. Log
4. Queue

Answer: B) Function

Explanation:

A function of the input determines how long an algorithm will take to execute.

---

11. The size of the input is characterized by ____ rather than directly dealing with it?

1. Functions
2. Values
3. Parameters
4. None

Answer: C) Parameters

Explanation:

The size of the input is characterized by parameters rather than directly dealing with it.

---

12. An algorithm's time complexity can be determined in ____ cases, since this is a difficult process?

1. Two
2. Three
3. Four
4. Five

Answer: B) Three

Explanation:

An algorithm's time complexity can be determined in three cases, since this is a difficult process.

---

13. What is/are the case(s) the Q12 is referring to?

1. Worst case
2. Best case
3. Average case
4. All of the above

Answer: D) All of the above

Explanation:

The cases Q12 is referring to are worst, best and average case.

---

14. The Worst-Case is represented by f (n), which is the ____ number of steps on all instances of size n?

1. Minimum
2. Average
3. Maximum
4. None

Answer: C) Maximum

Explanation:

The Worst-Case is represented by f (n), which is the maximum number of steps on all instances of size n.

---

15. The Best-Case is represented by f (n), which is the ____ number of steps on all instances of size n

1. Minimum
2. Average
3. Maximum
4. None

Answer: A) Minimum

Explanation:

The Best-Case is represented by f (n), which is the minimum number of steps on all instances of size n.

---

16. Algorithm ____ times are described using asymptotic notations?

1. Running
2. Execution
3. Stagnate
4. Fragile

Answer: B) Execution

Explanation:

Algorithm execution times are described using asymptotic notations.

---

17. Notations indicate the ____ in which functions grow?

1. Base
2. Order
3. Line
4. Circle

Answer: B) Order

Explanation:

Notations indicate the order in which functions grow.

---

18. Which of the following is/are an/the asymptotic notation?

1. θ
2. Ω
3. W
4. All of the above

Answer: D) All of the above

Explanation:

θ, Ω,w are all asymptotic notation.

---

19. When c and n0 are positive constants, f (n) ≤ C x g (n) for all n, n ≥ n0 gives the function ____?

1. f (n) =O ((n))
2. f (n) = o (g (n))
3. f (n) =O (g (n))
4. f (n) =O (g (C))

Answer: C) f (n) =O (g (n))

Explanation:

When c and n0 are positive constants, f (n) ≤ C x g (n) for all n, n ≥ n0 gives the function f (n) =O (g (n)).

---

20. The function f (n) = Ω (g (n)) if and only if exist positive constant c and n₀ such that ____ for all n, n ≥ n₀?

1. f (n) ≥ C* g (n)
2. f (n) ≤ C* g (n)
3. f (n) ≥ g (n)
4. f (n) ≤ g (n)

Answer: A) f (n) ≥ C* g (n)

Explanation:

The function f (n) = Ω (g (n)) if and only if exist positive constant c and n₀ such that f (n) ≥ C* g (n) for all n, n ≥ n₀.

---

21. The function f (n) = θ (g (n)) [read as "f is the theta of g of n"] if and only if there exists positive constant k₁, k₂ and k₀ such that ____ for all n, n≥n_0?

1. f (n) ≥ C* g (n)
2. f (n) ≤ C* g (n)
3. f (n) ≥ g (n)
4. f (n) ≤ g (n)

Answer: B) f (n) ≤ C* g (n)

Explanation:

The function f (n) = θ (g (n)) [read as "f is the theta of g of n"] if and only if there exists positive constant k₁, k₂ and k₀ such that k₁* g (n) ≤ f (n)≤k₂* g(n)for all n, n≥n₀.

---

---