2) Given two sorted arrays. There is only 1 difference between the arrays. First array has...

Transcribed Image Text:

2) Given two sorted arrays. There is only 1 difference between the arrays. First array has one element extra added in between. The goal is to find the index of the extra element. Examples: The first array has an extra element 9. The extra element is at index 5. Input: {2, 4, 6, 8, 9, 10, 12}; {2, 4, 6, 8, 10, 12}; Output: 5 You will get the full credit of this question if you solve it in O(logn) with a divide-and-conquer method. 70% of credit is given to solutions with complexity of O(n) and O(nlogn). Solutions with O(n) or slower will get 50% of credit. a) Write pseudo-code. (20 pts) b) What is the time complexity of your algorithm? (5 pts) 2) Given two sorted arrays. There is only 1 difference between the arrays. First array has one element extra added in between. The goal is to find the index of the extra element. Examples: The first array has an extra element 9. The extra element is at index 5. Input: {2, 4, 6, 8, 9, 10, 12}; {2, 4, 6, 8, 10, 12}; Output: 5 You will get the full credit of this question if you solve it in O(logn) with a divide-and-conquer method. 70% of credit is given to solutions with complexity of O(n) and O(nlogn). Solutions with O(n) or slower will get 50% of credit. a) Write pseudo-code. (20 pts) b) What is the time complexity of your algorithm? (5 pts)

Answer rating: 100% (QA)

a Pseudocode for finding the index of the extra element in two ... View the full answer