I know an array access is O(1) constant time but I am curious if this logic applies for multiple accesses.
Loop(Index i)
{
if A[i] > 5
{
count ;
if A[i 1] > 5
Loop(i 1)
if A[i 2] > 5
Loop(i 2)
}
}
I know this code is not complete, redundant, and never-ending but I am just trying to understand logic of Big O and array access. This loop has 3 array accesses, each at O(1). So 3*O(1) = O(3) = O(1). Is this idea correct?
CodePudding user response:
Yes; the time complexity of a single array access is constant, even if there are other ones in its vicinity. 3 is a constant, so the overall complexity doesn't increase. If you instead had n
array accesses, the time complexity would become O(n)
.