Construct an algorithm involving sorting, selection, or divide and conquer. a)Suppose we are given an array A[1...n] >=
Posted: Fri Jul 01, 2022 5:43 am
Construct an algorithm involving sorting, selection, or divideand conquer.
a)Suppose we are given an array A[1...n] >= n in advance.Describe a constant time algorithm that either computes an index isuch that A =i or correctly reports that no such index exists.Briefly explain your reasoning.
b) Describe a O(logn) algorithm that either computes an index isuch that A = i or correctly reports that no such index exists.You do not have to formally prove correctness, but explain yourreasoning. Briefly justify the running time.
a)Suppose we are given an array A[1...n] >= n in advance.Describe a constant time algorithm that either computes an index isuch that A =i or correctly reports that no such index exists.Briefly explain your reasoning.
b) Describe a O(logn) algorithm that either computes an index isuch that A = i or correctly reports that no such index exists.You do not have to formally prove correctness, but explain yourreasoning. Briefly justify the running time.