Register

Let A =[a1, a2, …, an] be a one-dimensional array of integers define a MEGA-PEAK

• edited by
969 views
1 votes
1 votes

Let A =[a1, a2, …, an] be a one-dimensional array of integers define a MEGA-PEAK in A to be an element ai belongs A such that ai >= aj for all aj with | j – i | <= 2. What is the time complexity to find MEGA-PEAK?

  1.   O(n)
  2.   O(n2)
  3.   O(log n)
  4.   O(n log n)
• edited by
User Avatar

1 Answer

1 votes
1 votes

Getting O(logn).

  1. Find mid as (low+high)/2.
  2. Check a[mid] with exactly 2 rightmost & leftmost elements. If it is maximum you get MegaPeak. If it's not then,
  3. If maximum element you got in step 2 was in right side set low = mid. If it was in left side set high = mid.
  4. Keep repeating 1, 2 & 3 till you get MegaPeak.
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
0 answers
1
Sahil Gupta asked Nov 25, 2014
765 views
Let X be the random variable on the set of permutations of a set of n distinct integers {a 1 , a 2 , . . . , a n } with a1 < a2 < · · · < an such that X(P) equals the number of comparisons used by the bubble sort to put these integers into increasing order.
Answer the following part:a) Show that, under the assumption that the input is equally likely to be any of the n! permutations of theseintegers, the average number of com...
User Avatar
0 votes
0 votes
1 answer
3
radha gogia asked Aug 15, 2015
701 views
Consider a relational table r with sufficient number of records, having attributes A1, A2,…, An and let 1 <= p <= n.
The database can be configured to do ordered indexing on Ap or hashing on Ap. Which of the following statements is TRUE?(A) Ordered indexing will always outperform hashin...
User Avatar
0 votes
0 votes
0 answers
4
. asked Feb 24, 2017
754 views
Let X={a1,a2,...,a7} be a set of seven elements and Y={b1,b2,b3} a set of three elements.
Let X={a1,a2,...,a7} be a set of seven elements and Y={b1,b2,b3} a set of three elements. The number of functions f from X to Y such that {i} f is onto and {ii}there are exactly three statements x in X such that f(x)=b1,is
Let X={a1,a2,...,a7} be a set of seven elements and Y={b1,b2,b3} a set of three elements. The number of functions f from X to Y such that {i} f is onto and {ii}there are ...
User Avatar
Link Copied!