Problem 1: Let A = [a1, a2, . . . , an] be an array of different integers and suppose thatthere exists an (unknown) index k such that the subarray [a1, a2, . . . , ak] is sorted in strictlyincreasing order (that is, if 1 ≤ i < j ≤ k, then ai < aj ), and the subarray [ak, ak+1, . . . , an]is sorted in strictly decreasing order (that is, if k ≤ i < j ≤ n, then ai > aj ). We wouldlike to find an index k.(i) Show that any comparison-based algorithm that solves this problem needs at leastΩ(log n) comparisons.(ii) Describe an optimal algorithm that solves this problem.

Problem 1: Let A = [a1, a2, . . . , an] be an array of different integers and suppose thatthere exists an (unknown) index k such that the subarray [a1, a2, . . . , ak] is sorted in strictlyincreasing order (that is, if 1 ≤ i < j ≤ k, then ai < aj ), and the subarray [ak, ak+1, . . . , an]is sorted in strictly decreasing order (that is, if k ≤ i < j ≤ n, then ai > aj ). We wouldlike to find an index k.(i) Show that any comparison-based algorithm that solves this problem needs at leastΩ(log n) comparisons.(ii) Describe an optimal algorithm that solves this problem.

Similar questions

I need help the question
I need the algorithm, proof of correctness and runtime analysis for the problem. No code necessary ONLY algorithm. And runtime should be O(n^2).
Write Algorithm for Minimal partition given a pair of pointsInput : a group G generated by S = {s 1, s2 ..... Sm} acting on a set s = { 1,2 ..... n }; two points co i < 0>2 of f2;Output : the finest invariant partition fof f~ such the the points co I and co 2 are in the same subset;
Interchange Base Points AlgorithmOutput: a base B = [131,132..... 13j-1, 13L.+1, 13j, 13j+2, 13j+3..... 13k] for G; a strong generating set relative to B; procedure interchange(var B: sequence of points; vat S: set of elements; j: 1..k-1);Interchange Base Points AlgorithmInput: a group G; a base [131,132..... 13k] for G and a strong generating set; an integer j between 1 and k-l; Output: a base [131,132..... 13k] for G and a strong generating set.
Problem 2: Finding an element.(i) Let n be an even positive integer. Let A be an array containing n not necessarydifferent integers. Elements in A are not necessary sorted. Describe an algorithmwhich in time O(n) tests whether there exists an element x in A that appears in Aat least n/2 times.(ii) Let S be a set containing n integers. An element x ∈ S is an approximate median ofS, if|{y ∈ S | y < x}| ≥ n/4and |{y ∈ S | y > x}| ≥ n/4Given an array A containing n different integers, not necessary sorted, describe analgorithm which in time O(n) finds all approximate medians of the set {A[i] | i =1, 2, . . . , n}.
Suppose that the maximum subarray sum (S) for A[0..k − 1] as well as the maximum sum for a subarray that ends at A[k − 1] (E) are known. Show how to extend S and E to include one more element A[k].