Algorithms Flashcards
What is recursion?
Recursion is breaking down a problem into subsets of the same problem.
What is a recursive function?
A recursive function is a function that calls itself.
What is a base case in recursion?
A base case is a condition that stops the recursive function from calling itself.
What happens when the base case is reached in recursion?
Once the base case is reached, the function returns a value.
What is recursion depth?
Recursion depth is how many times the recursive function has been called.
What is the maximum recursion depth in Python?
Python has a maximum recursion depth of 1000.
What is an advantage of using recursion?
Recursion can lead to less code and more elegant, efficient solutions.
What is a disadvantage of using recursion?
Recursion can be difficult to understand.
What is the Fibonacci sequence?
The Fibonacci sequence is a series where each number is the sum of the two preceding ones, starting with 0 and 1.
What is linear search?
Linear search checks each element in the list one by one until the target is found.
What is the time complexity of linear search?
The time complexity of linear search is O(n).
What is binary search?
Binary search divides the list into halves repeatedly until the target element is found.
What is the time complexity of binary search?
The time complexity of binary search is O(log n).
What is selection sort?
Selection sort finds the smallest item in a list and places it at the correct position.
What is the time complexity of selection sort?
The time complexity of selection sort is O(n²) in the worst, average, and best cases.
What is insertion sort?
Insertion sort inserts each item one at a time into its correct position.
What is the time complexity of insertion sort?
The time complexity of insertion sort is O(n²) in the worst, average, and best cases.
What is bubble sort?
Bubble sort iterates through a list comparing pairs of items and swaps them if they are in the wrong order.
What is the time complexity of bubble sort?
The time complexity of bubble sort is O(n²).
What is quicksort?
Quicksort selects a pivot and partitions the list into two sub-lists based on whether elements are less than or greater than the pivot.
What is the average case time complexity of quicksort?
The average case time complexity of quicksort is O(n log n).
What is the worst-case time complexity of quicksort?
The worst-case time complexity of quicksort is O(n²).
What is time complexity?
Time complexity refers to the computational time taken by an algorithm relative to the input size.
What are the types of time complexity?
Best case, worst case, and average case time complexity.
What is a characteristic of Quick Sort regarding stability?
Quick Sort is not a stable sorting algorithm, meaning it may change the relative order of equal elements.
How does Quick Sort compare to Bubble Sort, Selection Sort, and Insertion Sort?
Quick Sort typically offers better average-case performance with O(n log n) time complexity.
When might Quick Sort not be suitable?
Quick Sort may not be suitable for small lists or nearly sorted lists due to its potential for worst-case performance.
What are Comparison-based sorting algorithms?
Comparison-based sorting algorithms include Selection Sort, Insertion Sort, and Bubble Sort. They rely on comparing elements of the list and swapping them based on their values.
What is a characteristic of Comparison-based sorting algorithms?
They typically have quadratic time complexity and do not employ any divide-and-conquer strategies.
What are Divide-and-conquer sorting algorithms?
Divide-and-conquer sorting algorithms include Quick Sort.
How does Quick Sort work?
Quick Sort works by selecting a ‘pivot’ element from the list and dividing the other elements into two sub-lists according to whether they are less than or greater than the pivot.
What is the average-case time complexity of Quick Sort?
Quick Sort typically has a better average-case time complexity compared to comparison-based algorithms.
