Awesome q2a theme
0 votes
98 views

in ‘Chiluvuru’ village there are many mathematicians and algorithm experts. They are always playing with numbers. In that village there is a young student and his name is Bahubali. He is interested in sorting algorithms. So, he taken a sorted array of n elements which has been circularly shifted. For example, {20,25,1,5,10,15} is a sorted array that has been circularly shifted by 2 positions. He want to find the largest element in a circularly shifted array. Here, there is a small constraint that the number of positions through which it has been shifted is unknown. He confuse to get a time complexity, so, try to help him to find time complexity.

1.

O(nlogn)

 

2. 

O(logn)

 

3.

O($n^2$)

 

4. 

O(n)

in Compiler Design by (699 points) | 98 views
0
is it O(n)?
0
can't we use binary search ?
0
how?
0
Take the middle element, check with adjacents.. If it is not maximum, then compare with starting element of array to traverse either left or right but need not to both sides
0
but, there is a shift operation, which means largest element could be any place.
0
I also gave modified binary search, right?
Take with examples.
0

@Shaik Masthan

U mean it is left shift, yes great then

But if shift also unknown.

I mean this example $5,4,3,1,7,8$

In this case ??

0
0
Can we apply max-min algorithm?

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users 2020 Aug 10 - 16
  1. Arkaprava

    40 Points

  2. jayeshasawa001

    11 Points

  3. Nilabja Sarkar

    8 Points

  4. siddharths067

    4 Points

  5. 404 found

    3 Points

  6. shashankrustagi2021

    2 Points

  7. Ashutosh777

    2 Points

  8. Mellophi

    2 Points

  9. sparshgarg

    1 Points

  10. sonam13

    1 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Mellophi

    152 Points

  2. Ashutosh777

    78 Points

  3. anurag sharma

    48 Points

  4. Arkaprava

    40 Points

  5. jayeshasawa001

    16 Points

  6. Kushagra गुप्ता

    15 Points

  7. Shaik Masthan

    13 Points

  8. srestha

    13 Points

  9. shashankrustagi2021

    12 Points

  10. munishchaturvedi

    10 Points

7,745 questions
1,844 answers
11,190 comments
95,103 users