In: Computer Science
1. Given three arrays of N names each, describe an O(nlogn) algorithm
to determine if there is any name common to all three arrays, and if so, return the first such name.?
2. Given an input array with all equal values, compare the following sorting algorithm using big-O notation.
Running Time |
Space Complexity |
|
Merge Sort |
||
Quick Sort |
||
Heap Sort |
The following algorithm takes O(NlogN) in sorting and O(N +N +N) in finding the intersection of three arrays. Thus the total running time is O(NlogN), taking the dominant term.
The solution for 2. part is below: Note: the answers depend heavily on the implementation of the sorting algorithms.