Understanding Complexity and Sorting

What is the time complexity of bubble sort in the worst case?

• O(n)

• O(n^2)

• O(log n)

• O(n log n)

Explain the difference between stable and unstable sorting algorithms.

• Stable sorting algorithms can sort only strings.

• Stable sorting algorithms are faster than unstable ones.

• Stable sorting algorithms preserve the order of equal elements; unstable sorting algorithms do not.

• Unstable sorting algorithms can only sort numbers.

What is the Master Theorem used for in algorithm analysis?

• The Master Theorem is used to analyze the time complexity of divide-and-conquer algorithms.

• To classify algorithms based on their input size.

• To optimize the performance of iterative algorithms.

• To determine the space complexity of algorithms.

Describe the time complexity of merge sort.

• O(n log n)

• O(n)

• O(log n)

• O(n^2)

How does quicksort's average case time complexity compare to its worst case?

• Average case is O(n log n), worst case is O(n^2).

• Average case is O(n^2), worst case is O(n log n).

• Both average case and worst case are O(n log n).

• Average case is O(n), worst case is O(n^2).

What is the significance of Big O notation in analyzing algorithms?

• Big O notation is used to measure the speed of a computer.

• Big O notation provides exact run times for algorithms.

• Big O notation is significant for analyzing algorithms as it allows for the evaluation of their efficiency and scalability.

• Big O notation is only relevant for sorting algorithms.

Provide an example of a divide and conquer algorithm.

• Quick Sort

• Dynamic Programming

• Binary Search

• Merge Sort

What are the best and worst case time complexities of insertion sort?

• Best case: O(n log n), Worst case: O(n^2)

• Best case: O(n^2), Worst case: O(n^3)

• Best case: O(1), Worst case: O(n)

• Best case: O(n), Worst case: O(n^2)

How can the Master Theorem be applied to solve recurrences?

• The Master Theorem applies only to iterative algorithms.

• The Master Theorem provides a method to analyze the time complexity of divide-and-conquer recurrences.

• The Master Theorem can only be used for non-recursive functions.

• The Master Theorem is used to solve linear equations.

What is the time complexity of heap sort?

• O(n)

• O(n log n)

• O(log n)

• O(n^2)