Ace Test Series: Algorithms - Time Complexity & Array

Question

An array $'A'$ has $n$ distinct integers. What is the tightest time complexity to check $A[i]=i$ for some $i$. Consider all elements of array within range from $1$ to $n$.

• A. $O(n^2)  $
• B. $O(1)$
• C. $O(n)$
• D. $O(logn)$

Comments

@ Subham

then do it for

0,1,2,3,4,9

how much time u need to check?

---

O(n)??

---

yes..

Answer 1

O(logn) is correct In case of sorted array. 

o(n) in case of unsorted array. 

Comments

yes by using binary search(divide & conquer ) approach we can find index corresponding to array element

so O(logn)

---

@abhishekmehta4u, @akshat sharma If array is already sorted,then don't we require just a constant time ? (since all the elements will meet the required condition) 

Answer 2

Answer should be O(n) if Array is unsorted as we need to go element by element and check if A[i] == i

if the given array is sorted then we could solve in O(1) because elements are from 1 to n and if array is starting from index 0 then we can directly return

FALSE ( there is no such element in the array where A[i] == i )

if array is starting from index 1 then A[1] == 1 so return TRUE

Answer 3

The above question will be solved in O(n) time since our input is not sorted.

Apply linear search, So, O(n).

If the input would have been in sorted order we could have just applied Binary Search on index and got the answer in O(log n) time.

I hope it helps :)

Comments

Nice one !!