Made Easy Test Series

Question

Given a sorted array of distinct integers A[1,2,3,..,n], the tightest upper bound to check the existence of any index i for which A[i]= i is equal to O($n^{a}log^{b}n)$. Then a+10b is equal to ___?

Comments

https://gateoverflow.in/286495/me-test-series?show=286536#c286536

---

1?

a= 1, b= 0

---

Magma shouldnt it take O(1) time? because it is already said that the array is in sorted order..

So if the array is in ascending order, then we will first check A[1] is 1 or not..if it is 1, then we can straight away say that there is existence of such an index. Or else there wont be any such index found since array is sorted and consists of distinct integers.

Same is the case with an array sorted in descending order. We will whether A[n] is equal to n or not.

So it will take O(1) time.

Isnt this correct?

---

Ouuh I gave you the wrong link :p

wait I checked this question properly

---

Somoshree Datta 5

I think it will take $O(logn)$ time.

Because the question is asking to check the existence of i such that A[i] = i.

it can't be O(1) time.

When there will be elements like this.

                            10 20 30 40 50.

remember question is asking for to check any index. So, worst case it has to check in all the sorted array.

 

---

kumar.dilip while checking the  first element itself we can say that no such element will exist anywhere else in the array since it is said that the array is in ascending order and has distinct integers.

---

Somoshree Datta 5

you're thinking in a wrong way

---

Magma where am I going wrong?pls explain :3

---

example :    2    2     2    5    10

here 3rd  element is 2 which  present at index a[2] = 2

So , it satisfy the condition right ??

---

Magma

sorted array of distinct integers

See this

---

-1   0    2   5    6  ???

3rd element 2 is at index 2

---

if we consider linear search on a shorted array then it will take O(n) times in worst case scenario but in case of binary search it will take O(log n) time

---

they apply Binary search ... but my question is how we  implement this algo by binary search ?? .. I  have not  any idea :3

https://stackoverflow.com/questions/4101141/algorithm-to-find-if-there-is-any-i-so-that-arrayi-equals-i

if any one understand than please explain me !!

---

Binary search needs to be implemented in this way:

check for the middle element first...if A[mid]=mid, then return true

else if A[mid]>mid, then check in the left half of the array since such an element cant be present in the right half anymore

or else check in the right half of the array

---

Yup great :D

---

@Magma  

yes but this is for single element check right ?

e.g : 

is a[1]=1 exist ?
took logn time
if no..then, 

is a[2] = 2 exist ? 
took another logn time 

likewise...we have to check for every element in worst case if no such index exist. 

which in turns give O(nlogn) which is not better than 
O(n) if linear search is done.
Please check.
@sanjayrao609

---

i too think answer should be  1 for this as a=1,b=0;

this is one of the application of binary search, and since tightest upper bound is asked so it must be O(n)

hence a=1

@Somoshree Datta 5

@Magma pls chk

Answer 1

If the array had A[i]=i,∀iA[i]=i,∀i, then the complexity would have been θ(1)θ(1) as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like 1,3,4,8,9,121,3,4,8,9,12 as well.

The question is asking to find an element A[i]A[i] in the sorted list which is situated at the index ii.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on i<A[i]i<A[i] - if it's true update high=mid-1 else if i>A[i]i>A[i] update low=mid+1. The complexity is indeed θ(log2n)

https://cs.stackexchange.com/questions/108642/finding-an-element-in-array-whose-index-number-and-element-value-same