Question

2. Design a deterministic algorithm to solve the following problem.
input: An array A[1...n] of n integers.
output: Two different indices i and j such that A[i] = A[j], if such indices exist.
Otherwise, return NONE.
Your algorithm must take O(n log(n)) time. You must describe your algorithm in plain English (no pseudocode) and you must explain why the running time of your algorithm is O(n log(n)).

Answer 1

This can be Done using Binary Search Algorithm wherein we will take each element of the array and Search for that element using the Binary search approach in the binary search approach we have to divide the sorted array into halves and compare the element to be searched to the middle element of the array sorted in ascending order.This has to be done recursively until we find an index j which matches the condition A[i] = A[j] such that i != j.

The complexity of this approach will be n log n as binary search divides the array into two halves each time until the element is found therefore it will take log n complexity where the base of Log is 2, and we are doing this for every element in the array for the worst case which gives the total complexity of the approach as n * log n.