programming in **Java** help please: You receive a list of integers, one at a ti
ID: 3678132 • Letter: P
Question
programming in **Java** help please:
You receive a list of integers, one at a time, a1,a2,… find the first time an ai comes up that has occurred previously, i.e. find the smallest i such that all the a1, a2, …, ai-1 are distinct but ai = aj for some 1 ? j < i. However, we do not have the nice repetitive structure past position j that aj+k = ai+k for all k ? 0. (This allowed us to obtain an O(i) time algorithm in HW-2.)
Describe an O(i log2 1 time algorithm to find the smallest i. ( Give an algorithm in recursive form and show its running time using the Master Theorem.) Note- running time is not a function of the global number of elements but only a function of the position of the first repetition. Hints: Combine merge-sort, binary search and let yourself be inspired by the expansion process of ArrayLists...Explanation / Answer
Algorithm, described above, is probabilistic and works in O(N log N) time on average. Its worst case complexity is O(N2). The alternative with a binary search tree may have O(N log2 N) worst case complexity if tree is self-balancing.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.