Big-O Notation

Question 1

What is a major drawback of the Empirical Method for measuring algorithm efficiency?
A. It only measures space efficiency.
B. It is dependent on the runtime environment and machine.
C. It is too expensive.
D. It does not account for the input size.

Answer 1

B. It is dependent on the runtime environment and machine.

Question 2

According to the provided resources, what are the most important properties of a good algorithm?
A. Generality and Efficiency
B. Time and Space
C. Correctness and Generality
D. Correctness and Efficiency

Answer 2

C. Correctness and Generality

Question 3

The Theoretical Method measures an algorithm’s efficiency in units based on what?
A. A basic operation and storage space.
B. Time and space used on a specific machine.
C. The programming language used.
D. The amount of code written.

Answer 3

A. A basic operation and storage space.

Question 4

Why is the Theoretical Method considered more controlled than the Empirical Method?
A. It is language and machine-independent.
B. It can be used for any problem.
C. It is more cost-effective.
D. It is a newer method.

Answer 4

A. It is language and machine-independent.

Question 5

Why is the theoretical method of algorithm analysis considered superior to the empirical method for comparing two different algorithms?
A. It accounts for all external factors, such as hardware and programming language, in its final result.
B. It provides a universal, machine-independent measure of efficiency that accurately predicts performance trends for large inputs.
C. It is faster to perform, as it doesn’t require writing and running code.
D. It only considers the best-case scenario, which is the most reliable for real-world applications.

Answer 5

B. It provides a universal, machine-independent measure of efficiency that accurately predicts performance trends for large inputs.

Question 6

Which of the following is a key difference between the empirical and theoretical methods of measuring efficiency?
A. The empirical method is used for small inputs, while the theoretical method is used for large inputs.
B. The empirical method measures time, while the theoretical method measures space.
C. The empirical method measures efficiency in a runtime environment, while the theoretical method measures it detached from the runtime environment.
D. The empirical method is based on the algorithm, while the theoretical method is based on the program.

Answer 6

C. The empirical method measures efficiency in a runtime environment, while the theoretical method measures it detached from the runtime environment.

Question 7

Which of the following best describes the relationship between an algorithm’s correctness, generality, and efficiency?
A. Correctness and generality are components of efficiency.
B. All three properties are of equal importance.
C. Correctness and generality are the most important properties, with efficiency being a secondary but still very important property.
D. Efficiency is the most important property because a correct algorithm is useless if it is too slow.

Answer 7

C. Correctness and generality are the most important properties, with efficiency being a secondary but still very important property.

Question 8

A theoretical analysis determines that Algorithm A is and Algorithm B is . Based on the principle that “Theoretically more efficient are usually empirically more efficient,” what can you most confidently predict about their real-world performance?
A. The analysis is only valid if both algorithms are written in the same programming language.
B. Algorithm A will always run faster than Algorithm B.
C. Both algorithms will have similar performance, as theoretical analysis is not always accurate.
D. For very small inputs, Algorithm A might be faster, but for large inputs, Algorithm B will be significantly faster.

Answer 8

D. For very small inputs, Algorithm A might be faster, but for large inputs, Algorithm B will be significantly faster.