Test Flashcards
What is the difference between an iterative algorithm and a recursive algorithm?
Iterative - uses loops to repeat a set of instructions until a condition is met
Recursive - solves a problem by calling itself with a smaller or simpler version of the original problem
What is a recursive algorithm’s base case? What is the recursive case?
Base - the simplest, smallest instance of the problem that can be solved directly without further recursion.
Recursion - the part of the algorithm that breaks the problem into one or more smaller subproblems and calls itself to solve these subproblems
What type of recursive method do you think would be more difficult to debug: one that uses direct recursion or one that uses indirect recursion? Why?
Indirect recursion is generally more difficult to debug due to the added complexity in following the call sequence across multiple functions.
Which repetition approach is less efficient: a loop or a recursive method? Why?
Generally, recursion is less efficient than iteration (loops) because of the additional overhead associated with multiple function calls.
When recursion is used to solve a problem, why must the recursive method call itself to solve a smaller version of the original problem?
Solving a smaller version of the problem at each step reduces its complexity until the base case is reached
How is a problem usually reduced with a recursive method?
Split the original problem, solve the smaller instances using a recursive call, and then combine the results
If a sequential search method is searching for a value that is stored in the last element of a 10,000-element array, how many elements will the search code have to examine to locate the value?
It will examine all 10,000 elements
In an average case involving an array of n elements, how many array elements does a sequential search algorithm have to access to locate a specific value?
In the average case, a sequential search examines about n/2 elements.
A binary search method is searching for a value that is stored in the middle element of an array. How many array elements have to be examined before finding the value?
It will examine 1 element—the middle element—since the binary search checks the midpoint first.
What is the maximum number of comparisons that a binary search method will make when searching for a value in a 1,000-element array?
Approximately 10 comparisons.
Why is the bubble sort inefficient for large arrays?
Because its O(n²) time complexity leads to a very high number of comparisons and swaps, making it inefficient for large arrays.
Under what conditions might the insertion sort be more efficient than the bubble sort?
When the array is nearly sorted, because insertion sort requires fewer shifts and comparisons in such cases, making it more efficient than bubble sort.
