Design and Analysis of Algorithms Quiz

What does time complexity measure in an algorithm?

• Number of lines of code

• Number of operations executed

• Amount of memory used

• Input size

Which of the following best describes space complexity?

• The number of times an algorithm loops

• The number of inputs an algorithm can handle

• The amount of time an algorithm takes to run

• The amount of memory an algorithm requires to execute

What is the time complexity of a binary search algorithm?

• O(1)

• O(n)

• O(log n)

• O(n^2)

What does Θ(n) represent in asymptotic notation?

• Average-case time complexity

• Best-case time complexity

• Tight bound on the time complexity

• Worst-case time complexity

What is the solution to the recurrence relation T(n) = 2T(n/2) + n?

• O(2^n)

• O(n log n)

• O(n)

• O(n^2)

What is the time complexity of merge sort in all cases?

• O(n^2)

• O(n)

• O(n log n)

• O(log n)

What is the worst-case time complexity of quick sort?

• O(n^2)

• O(n log n)

• O(log n)

• O(n)

What is the purpose of asymptotic notation in algorithm analysis?

• To precisely measure the exact number of operations in an algorithm

• To provide a rough estimate of algorithmic performance

• To compare algorithms based on their exact execution times

• To simplify the comparison of algorithms based on their growth rates

Which of the following is true about the relationship between O(n) and Ω(n)?

• O(n) is always greater than Ω(n)

• Ω(n) is always greater than O(n)

• O(n) and Ω(n) are equal

• There`s no relationship between O(n) and Ω(n)

Quick sort is an example of a sorting algorithm based on which strategy?

• Dynamic programming

• Greedy approach

• Divide and conquer

• Backtracking