Week 4 - Recursion and Divide and Conquer Flashcards
What is Divide and Conquer?
Divide and conquer is a problem-solving strategy that involves breaking a complex problem into smaller, more manageable parts, solving each part individually—often using recursion—and then combining the solutions to address the overall problem. The approach includes identifying a simple “base case” that can be solved directly.
What is an example of a problem where divide and conquer can be applied?
The farm division problem, where the goal is to find the largest size that can be used to divide a farm into square plots.
What is GCD?
The Greatest Common Divisor (GCD) is the largest number that divides two or more integers without leaving a remainder. It is used to simplify fractions and solve problems involving divisibility.
What is Quicksort?
Quicksort is a sorting algorithm that works by selecting a “pivot” element from the array, then partitioning the other elements into two sub-arrays: those less than the pivot and those greater than the pivot. It recursively applies the same process to the sub-arrays, ultimately sorting the entire array.
What is Partitioning?
Partitioning in quicksort is the process of rearranging the elements in an array such that all elements less than a chosen pivot are placed before it, and all elements greater than the pivot are placed after it. This step is crucial as it divides the array into two sub-arrays, each of which can then be recursively sorted.
What is a good strategy for choosing the pivot in quicksort?
Randomly choosing the pivot number results in the most effective
What is the worst case scenario for quicksort and what is the time complexity?
The worst case scenario for quicksort is when the newly selected pivot is the next element in order, in this case it has a time complexity of O(n^2), which is the same as selection sort!
What is the worst case time complexity?
Worst Case: Refers to the scenario in which an algorithm takes the maximum steps to complete its tasks.
What is the average case time complexity?
Average Case: Represents the expected performance of an algorithm on a typical or random distribution of inputs.
What is the average case scenario for quicksort and what is the time complexity?
In the average case, Quicksort partitions the array much more evenly. So, the call stack is shorter! It It has a time complexity of O(n log n).
