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

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