Search code examples
arraysbig-oanalysis

Big O - Array Access in Loop


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?


Solution

  • 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).