Module 4 Flashcards
In this type of approach, the problem is divided into smaller sub-problems and then solved independently.
Divide and Conquer
In this type of approach, once those “atomic” smallest possible sub-problem (fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the solution of an original problem.
Divide and Conquer
What are the three steps in the Divide and Conquer process?
- Divide/Break
- Conquer/Solve
- Merge/Combine
In this stage of the Divide and Conquer process, the problem is broken into smaller subproblems.
Divide/Break
In this stage of the Divide and Conquer process, a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered ‘solved’ on their own.
Conquer/Solve
This stage of the Divide and Conquer process recursively combines them until they form a solution of the original problem.
Merge/Combine
This type of sorting algorithm divides the array into equal halves and then combines them in a sorted manner.
Merge Sort
This sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then it combines the smaller sorted lists keeping the new list sorted too.
Merge Sort
What is the worst-case time complexity of merge sort?
Ο(n log n)
This is a highly efficient sorting algorithm and is based on
partitioning of array of data into smaller arrays.
Quick Sort
This type of sorting algorithm partitions an array and then calls itself recursively twice to sort the two resulting subarrays.
Quick Sort
What is the best/average case time complexity of the Quick Sort technique?
O(n log n)
What is the worst case time complexity of the Quick sort technique?
O(n^2)
What is the space complexity of the Quick sort technique?
O(log n)
This type of algorithm looks for a particular item by comparing the middle most item. Halves the search into subarrays depending on where it is and returns the index if it is a match.
Binary Search
