QUIZ 1

Which of the following best describes the "worst-case" analysis of an algorithm?

• The fastest time an algorithm takes

• The maximum time on any input of size n

• The average time taken

• The space used by the algorithm

Answer explanation

The "worst-case" analysis of an algorithm refers to the maximum time it takes on any input of size n. This helps in understanding the upper limits of an algorithm's performance, making it crucial for evaluating efficiency.

What is the Big O notation used for?

• Describing best-case performance

• Describing the exact running time

• Giving an upper bound of runtime

• Giving a lower bound

Answer explanation

Big O notation is used to describe the upper bound of an algorithm's runtime, indicating the worst-case scenario for performance. It does not provide exact running times or best-case scenarios.

Which asymptotic notation provides both an upper and lower bound?

• O

• Θ

• Ω

• o

Answer explanation

The correct choice is Θ (Theta) notation, which provides both an upper and lower bound for a function's growth rate. In contrast, O (Big O) provides only an upper bound, while Ω (Big Omega) provides only a lower bound.

What is the time complexity of the following loop?

• O(n)

• O(log n)

• O(n²)

• O(2^n)

Answer explanation

The loop has a nested structure, leading to O(n) iterations for each of the n elements, resulting in O(n²) time complexity. Thus, the correct answer is O(n²).

Which efficiency class is faster for large inputs?

• O(n log n)

• O(n²)

• O(2^n)

• O(n!)

Answer explanation

O(n log n) is more efficient than O(n²), O(2^n), and O(n!) for large inputs. As input size increases, O(n log n) grows slower, making it the fastest choice among the options provided.

What is the recurrence relation for Merge Sort?

• T(n) = T(n-1) + O(n)

• T(n) = 2T(n/2) + O(n)

• T(n) = T(n/2) + O(1)

• T(n) = T(n-1) + O(1)

Answer explanation

Merge Sort divides the array into two halves, recursively sorts them, and then merges the sorted halves. This leads to the recurrence relation T(n) = 2T(n/2) + O(n), where O(n) accounts for the merging process.

Which method is commonly used to solve recurrence relations in recursive algorithms?

• Divide-and-Conquer

• Loop Invariant

• Master Theorem

• Hashing

Answer explanation

The Master Theorem is a powerful tool for analyzing the time complexity of recursive algorithms by providing a method to solve recurrence relations, making it the correct choice for this question.

What does O(log n) signify?

• The algorithm grows linearly with input

• The algorithm processes input in constant time

• The algorithm doubles its time with each step

• The algorithm grows slowly even with large inputs

Answer explanation

O(log n) indicates that the algorithm's time complexity grows slowly as the input size increases, making it efficient for large inputs. This is in contrast to linear growth or constant time, which are represented by other complexities.

Would you like this content exported into Word documents similar to the originals?

Answer explanation

Yes, exporting the content into Word documents similar to the originals would maintain formatting and structure, making it easier to work with and share.

Which of the following recurrence relations represents the time complexity of Binary Search?

• T(n) = T(n/2) + O(1)

• T(n) = T(n/2) + T(n/4)

• T(n) = T(n-1) + O(1)

• T(n) = 2T(n/2) + O(1)

Answer explanation

The correct recurrence relation for Binary Search is T(n) = T(n/2) + O(1). This reflects that the search space is halved with each step, and O(1) accounts for the constant time operations at each level.