Time Complexity of finding the length of an array

Question

I am a little confused on what the time complexity of a len() function would be.

I have read in many different posts that finding the length of an array in python is O(1) with the len() function and similar for other languages.

How is this possible? Do you not have to iterate through the whole array to count how many indices its taking up?

Answer 1

Do you not have to iterate through the whole array to count how many indices its taking up?

No, you do not.

You can generally always trade space for time when constructing algorithms.

For example, when creating a collection, allocate a separate variable holding the size. Then increment that when adding an item to the collection and decrement it when removing something.

Then, voilà, the size of the collection can then be obtained in O(1) time just by accessing that variable.

And this appears to be what Python actually does, as per this page, which states (checking of the Python source code shows that this is the action when requesting the size of a great many objects):

Py_SIZE(o) - This macro is used to access the ob_size member of a Python object. It expands to (((PyVarObject*)(o))->ob_size).

---

If you compare the two approaches (iterating vs. a length variable), the properties of each can be seen in the following table:

Measurement	Iterate	Variable
Space needed	No extra space beyond the collection itself.	Tiny additional length (4 bytes allowing for size of about four billion).
Time taken	Iteration over the collection. Depends on collection size, so could be significant.	Extraction of length, very quick. Changes to list size (addition or deletion) incur slight extra expense of updating length, but this is also tiny.

In this case, the extra cost is minimal but the time saved for getting the length could be considerable, so it's probably worth it.

That's not always the case since, in some (rare) situations, the added space cost may outweigh the reduced time taken (or it may need more space than can be made available).

---

And, by way of example, this is what I'm talking about. Ignore the fact that it's totally unnecessary in Python, this is for a mythical Python-like language that has an O(n) cost for finding the length of a list:

import random

class FastQueue:
    """ FastQueue: demonstration of length variable usage.
    """
    def __init__(self):
        """ Init: Empty list and set length zero.
        """
        self._content = []
        self._length = 0

    def push(self, item):
        """ Push: Add to end, increase length.
        """
        self._content.append(item)
        self._length += 1

    def pull(self):
        """ Pull: Remove from front, decrease length, taking
                  care to handle empty queue.
        """
        item = None
        if self._length > 0:
            item = self._content[0]
            self._content = self._content[1:]
            self._length -= 1
        return item

    def length(self):
        """ Length: Just return stored length. Obviously this
                    has no advantage in Python since that's
                    how it already does length. This is just
                    an illustration of my answer.
        """
        return self._length

    def slow_length(self):
        """ Length: A slower version for comparison.
        """
        list_len = 0
        for _ in self._content:
            list_len += 1
        return list_len

""" Test harness to ensure I haven't released buggy code :-)
"""

queue = FastQueue()

for _ in range(10):
    val = random.randint(1, 50)
    queue.push(val)
    print(f'push {val}, length = {queue.length()}')

for _ in range(11):
    print(f'pull {queue.pull()}, length = {queue.length()}')