Big(0) constant time complexity

Question

I'm learning about Big(O). Below code is an example of O(1) constant time complexity

public class DSA {
    
    public static void main(String args[])
    {
        int ar[] = {1,2,3,4};
       System.out.println(fun(ar));
    }


    static int fun(int arr[])
    {
        return arr[0] * arr[arr.length - 1];
    }
  
}

But after learning O(n), I came back to this example and found that while calling length() method on my array, on the backend the length() method counts all the elements inside an array, So do we count that backend time complexity? If yes then the above example should be of O(n) but it's known as O(1). Kindly correct me if I'm wrong.

*"the backend the length() method counts all the elements inside an array"*, no, there is no `length()` but only `length` and that does not count anything, it already is the length — luk2302, Jul 14 '21 at 16:46

score 2 · Accepted Answer · answered Jul 14 '21 at 16:52

From the JLS

The members of an array type are all of the following:

The public final field length, which contains the number of components of the array. length may be positive or zero.

So length is a simple field. There are some languages that let you override field access (Python and Kotlin have properties, Ruby and Scala have unified field access, etc.), but Java is not one of those. A field in Java is always a literal field, not a function call. So accessing length will query a simple field, not do any additional work.

Hence, in Java at least, array length is O(1) since the length is cached and stored on the object at construction time. This is not true in every language, so your intuition is good. If we were in, say, Haskell, the length function counts the number of elements in a list and would be O(n). But in Java, it's still O(1).

score 1 · Answer 2 · answered Jul 14 '21 at 16:49

Yes we do count the "backend" complexity.

If computing arr.length is O(n), you are right: the whole is O(n).

Depending on the language and array/list implementation, the length might be known without traversing all elements and then it would be O(1).

Note: in Java arrays' length access is O(1).

Big(0) constant time complexity

2 Answers2