-Write two function templates, one iterative and one recursive, that search an a
ID: 3709409 • Letter: #
Question
-Write two function templates, one iterative and one recursive, that search an array of type T for a given element of type T and return true if found, else false. The functions take three parameters, the array to search, the element to seek, and the length of the array.
-What is the Big-O runtime of the following function to search for a duplicate value within an array? (Disclaimer: the code might not actually compile and run.)
bool FindMatch(int *array, int arrayLength) {
for (int i = 0; i < arrayLength; i++)
for (int j = i + 1; j < arrayLength; j++)
if(array[i] == array[j])
return true;
}
Here is another function to search for a duplicate value within an array (Disclaimer: the code won’t actually compile and run.)
bool FindMatch(int *array, int arrayLength) {
int *sortedArray = MergeSort(array, arrayLength); // Part A
for (int i = 0; i < arrayLength - 1; i++) // Part B
if(sortedArray[i] == sortedArray[i + 1])
return true;
}
a) What is the Big-O runtime of Part A?
b) What is the Big-O runtime of Part B?
c) What is the overall simplified Big-O runtime of the entire function?
Explanation / Answer
Given two function templates, one iterative and one recursive
bool FindMatch(int *array, int arrayLength) {
for (int i = 0; i < arrayLength; i++)
for (int j = i + 1; j < arrayLength; j++)
if(array[i] == array[j])
return true;
}
This function iterates through the array using nested loops and searches if there's any duplicate values.
So, time complexity of this function is O(N^2)
bool FindMatch(int *array, int arrayLength) {
int *sortedArray = MergeSort(array, arrayLength); // Part A
for (int i = 0; i < arrayLength - 1; i++) // Part B
if(sortedArray[i] == sortedArray[i + 1])
return true;
}
a. In the second function, mergeSort is a recursive method whose complexity is O(NlogN)
b. In part B, we are iterating through the sorted array and comparing with the previous element. Complexity of this is O(N).
c. So, total complexity is O(N LOG N) + O (N) = O(N LOG N)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.