why do we need O(n), we can do directy check if index is present or not in O(1) time. Please explain..

Question

Given an array of distinct integers A[1, 2,…n]. Find the tightest upper bound to check the existence of any index i for which A[i]= i.

(a) O (1)                                                                      (b) O (log n)

(c) O (n)                                                                      (d) None of these

Solution: Option (c)

Answer 1

The question asks us to find any i such that A[i] = i.

So we start from i, checking if A[1] = 1, A[2] = 2 and so on.

Thus, we will have to check till A[n] = n, making it $O(n)$ and not $O(1)$.

Answer 2

This is a linear search problem where in we check for index value and element at that index.It is not O(1) as it is not constant which is independent of the input size,here the above problem is dependent on the input size hence it cannot be O(1).

O(logn) is possible as we can do binary search to find elements but it is not tightest upper bound hence O(n)