DSA Module-4 Quiz

What is the purpose of algorithm analysis?

• The purpose of algorithm analysis is to assess the efficiency and performance of algorithms.

• To create new algorithms from scratch.

• To determine the best programming language for implementation.

• To visualize data structures in a graphical format.

Define asymptotic notation and give an example.

• An example of asymptotic notation is Big O notation, such as O(n^2), which describes an algorithm whose running time grows quadratically with the input size n.

• An example of asymptotic notation is Big Theta notation, such as Θ(n), which describes an algorithm with constant running time.

• Asymptotic notation is used to measure the exact running time of an algorithm, like O(n log n).

• An example of asymptotic notation is Little o notation, which indicates that an algorithm's running time is always less than a certain function.

What are the basic efficiency classes in algorithms?

• O(n^4)

• O(n!)

• O(3^n)

• O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n)

Explain the difference between recursive and non-recursive algorithms.

• Recursive algorithms call themselves to solve subproblems, while non-recursive algorithms use loops to iterate through operations.

• Recursive algorithms use loops to solve problems directly.

• Non-recursive algorithms call themselves to handle subproblems.

• Both recursive and non-recursive algorithms require the same amount of memory.

What is the time complexity of linear search?

• O(1)

• O(n)

• O(n^2)

• O(log n)

How does binary search improve efficiency over linear search?

• Binary search is more efficient than linear search because it reduces the search space by half with each comparison, resulting in O(log n) time complexity.

• Linear search has a time complexity of O(log n) which is faster than binary search.

• Binary search can only be used on unsorted data.

• Binary search checks every element sequentially like linear search.

What is the worst-case time complexity of binary search?

• O(log n)

• O(n log n)

• O(n)

• O(1)

Describe the mathematical analysis process for recursive algorithms.

• Ignoring base cases and focusing only on recursive cases

• The mathematical analysis process for recursive algorithms involves identifying base and recursive cases, establishing a recurrence relation, solving it, and verifying the solution.

• Using iterative methods instead of recursion

• Establishing a linear equation instead of a recurrence relation

What is the significance of Big O notation in algorithm analysis?

• Big O notation is used to measure the physical size of algorithms.

• Big O notation provides exact run times for algorithms.

• Big O notation is significant because it allows for the analysis and comparison of the efficiency of algorithms in terms of time and space complexity.

• Big O notation is only relevant for sorting algorithms.

Provide an example of a sorting algorithm and explain its efficiency.

• SelectionSort

• QuickSort

• InsertionSort

• BubbleSort