ADA Module-2 Quiz

What is the time complexity of the brute-force solution for the Traveling Salesman Problem (TSP)?

• O(n)

• O(n log n)

• O(n!)

• O(2ⁿ)

5. Insertion Sort uses which design paradigm?

• 5. Divide-and-Conquer

• 5. Decrease-by-One

• 5. Transform-and-Conquer

• 5. Greedy

5. Topological Sorting is applied to:

• 5. Arrays

• 5. Binary Trees

• 5. Directed Acyclic Graphs (DAGs)

• 5. Undirected Graphs

Arrange the steps of decrease-and-conquer:

I. Solve the smaller instance
II. Reduce the problem size
III. Combine results

• II → I → III

• I → II → III

• III → II → I

Decrease-and-conquer algorithms always reduce the problem size by half.

• True

• False

9. Merge Sort has a worst-case time complexity of:

• 9. O(n)

• 9. O(n²)

• 9. O(n log n)

• 9. O(log n)

9. Strassen’s Matrix Multiplication improves upon the standard O(n³) method by reducing the time complexity to:
   a)
   b)
   c)

• 9. O(n².81)

• 9. O(n² log n)

• 9. O(n³/log n)

Quick Sort’s worst-case time complexity is O(n log n).

• True

• False

How many permutations would a brute-force TSP solution evaluate for 4 cities?

• 23

• 24

• 12

• 4

Time Complexity searching an element using of Binary Trees is ?

• O(n)

• O(n²)

• O(n log n)

• O(log n)