Understanding python's len() time complexity

user_15535425 0
Viewed 248

I had a question about whether I was understanding the time complexity of the len function in Python correctly. I've seen multiple posts on this topic here and here but I feel like the answers didn't explicitly answer another question I had.

As I understand it, the time complexity of calling the len function is O(1) because the length of the object (e.g. an array) is stored behind the scenes. However, the time complexity of calling a function that isn't stored behind the scenes (e.g. max or min) is O(n) because we would have to search the entire array.

I'm wondering then, would it be correct to also think of the time complexity of len to be O(n) (because it takes n number of constant operations to keep track of the length of the array as we add or delete values from the array) but is only O(1) because we keep track of the length behind the scenes?

Technically, we should be able to store other information such as max and min while we create the array and accessing this information would also be O(1) if we explicitly save these values.

time-complexity python
3 Answers

len(obj) simply calls obj.__len__():

>>> [1, 2, 3, 4].__len__()
4

It is therefore not correct to say that len() is always O(1) -- calling len() on most objects (e.g. lists) is O(1), but an arbitrary object might implement __len__ in an arbitrarily inefficient way.

max(obj) is a different story, because it doesn't call a single magic __max__ method on obj; it instead iterates over it, calling __iter__ and then calling __next__. It does this n times (and also does a comparison each time to track the max item it's seen so far), so it must always be at least O(n). (It can be slower if __next__ or the comparison methods are slow, although that would be very unusual.)

For either of these, we don't count the time it took to build the collection as part of the cost of calling the operation itself -- this is because you might build a list once and then call len() on it many times, and it's useful to know that the len() by itself is very cheap even if building the list was very expensive.

user_37997590

We don't count the complexity of all the operations that increment and decrement the length field of the array, because they're not dependent on the current length of the array.

For instance, if you build up an array by appending and popping, you may have done far more than n iterations before you call len().

Furthermore, if you're calculating the complexity of the entire algorithm, you would have already accounted for the complexity of creating the array. You don't want to count it again when calculating the complexity of processing the array.

user_14918950

Let's check it:

import time
from matplotlib import pyplot as plt
import numpy as np


def main():
    a = []
    data = []
    for i in range(10_000):
        a.append(i)
        ts_len = time.time()
        _ = len(a)
        te_len = time.time()

        ts_max = time.time()
        _ = max(a)
        te_max = time.time()

        ts_min = time.time()
        _ = min(a)
        te_min = time.time()

        data.append([i, te_len - ts_len, te_max - ts_max, te_min - ts_min])

    data = np.array(data)
    plt.plot(data[:, 0], data[:, 1], "-r", label="len")
    plt.plot(data[:, 0], data[:, 2], "--g", label="max")
    plt.plot(data[:, 0], data[:, 2], ".b", label="min")
    plt.title("Len/max/min")
    plt.xlabel("Size of the list")
    plt.ylabel("Time elapsed (s)")
    plt.legend()
    plt.show()


if __name__ == '__main__':
    main()

Len/min/Max

user_26816620
Related