Algorithm Quiz

What is an algorithm?

• A single computational step

• A random set of instructions

• A complex mathematical equation

• A sequence of computational steps that transform input into output

What are the 5 basic properties of an algorithm according to D.E.Knuth?

• Input, Output, Finiteness, Definiteness, Effectiveness

• Input, Output, Finiteness, Clarity, Efficiency

• Input, Output, Complexity, Clarity, Effectiveness

• Input, Output, Finiteness, Definiteness, Efficiency

What is the space complexity of an algorithm?

• The order of growth of the algorithm

• The number of steps required to complete the algorithm

• The amount of memory needed to run the algorithm

• The amount of computer time needed to run the algorithm

What does Big-Oh notation represent?

• Exact solving of a problem

• Average case efficiency

• Upper bound of a function

• Lower bound of a function

What is the time complexity of a linear search algorithm in the best case scenario?

• O(1)

• O(n^2)

• O(n)

• O(log n)

What is the main difference between average case analysis and amortized analysis?

• Average case analysis considers worst case scenarios

• Amortized analysis considers best case scenarios

• Amortized analysis involves probability while average case analysis does not

• Average case analysis involves probability while amortized analysis does not

What does Theta notation represent?

• Exact solving of a problem

• Average case efficiency

• Both upper and lower bounds of a function

• Lower bound of a function

What is the time complexity of a binary search algorithm in the worst case scenario?

• O(log n)

• O(n)

• O(1)

• O(n^2)

What is the purpose of probabilistic analysis in algorithms?

• To determine the worst case scenario

• To find the best case efficiency

• To design efficient algorithms based on probability

• To analyze the average case performance

What is the main goal of amortized analysis?

• To find the average running time per operation over a worst case sequence

• To find the exact solving of a problem

• To determine the best case scenario

• To analyze the average case performance