0

I'm looking to iterate over every third element in my list. But in thinking about Big-O notation, would the Big-O complexity be O(n) where n is the number of elements in the list, or O(n/3) for every third element?

In other words, even if I specify that the list should only be iterated over every third element, is Python still looping through the entire list?

Example code:

def function(lst):
    #iterating over every third list
    for i in lst[2::3]:
        pass
yama
  • 17
  • 3
  • 1
    This would be O(n/3). Big-O notation is separate from physical implementation so it does not matter how python implements it so long as it. That being said, python only looks at every third element and completely ignores the rest. – Locke Nov 28 '21 at 00:18
  • 6
    Better question: Is there a difference between `O(n)` and `O(n/3)`? – Silvio Mayolo Nov 28 '21 at 00:20
  • It might be easier to think of it as only accessing every third index within the length of the list instead of in the context of the data structure holding those elements. – Locke Nov 28 '21 at 00:24
  • @Locke Why? No indices are involved, and your suggestion doesn't change the number of "things" iterated over, whatever you call them. – chepner Nov 28 '21 at 00:25
  • It doesn't change the BigO value, but as long as you are considering every detail and looking at the constants, remember that `lst[2::3]` needs to allocate a new list and copy values to it. – Mark Nov 28 '21 at 00:28
  • How does your function behave if you double the number of elements in the list? – sourcloud Nov 28 '21 at 00:29
  • 1
    Whether it creates a new list or not isn't relevant. It's O(n); at the two extremes it's a difference between `n/3` and `2n`, which is still just a constant factor of 6: it's O(n) either way. – chepner Nov 28 '21 at 00:39

2 Answers2

2

When using Big-O notation we ignore any scalar multiples out the front of the functions. This is because the algorithm still takes "linear time". We do this because Big-O notation considers the behaviour of a algorithm as it scales to large inputs.

Meaning it doesn't matter if the algorithm is considering every element of the list or every third element the time complexity still scales linearly to the input size. For example if the input size is doubled, it would take twice as long to execute, no matter if you are looking at every element or every third element.

Mathematically we can say this because of the M term in the definition (https://en.wikipedia.org/wiki/Big_O_notation):

abs(f(x)) <= M * O(f(x))

codesflow
  • 56
  • 4
0

Big O notation would remain O(n) here.

Consider the following:

n = some big number
for i in range(n):
  print(i)
  print(i)
  print(i)

Does doing 3 actions count as O(3n) or O(n)? O(n). Does the real world performance slow down by doing three actions instead of one? Absolutely!

Big O notation is about looking at the growth rate of the function, not about the physical runtime.

Consider the following from the pandas library:

# simple iteration O(n)
df = DataFrame([{a:4},{a:3},{a:2},{a:1}])
for row in df:
  print(row["a"])
# iterrows iteration O(n)
for idx, row in df.iterrows():
  print(row["a"])
# apply/lambda iteration O(n)
df.apply(lambda x: print(x["row"])

All of these implementations can be considered O(n) (constant is dropped), however that doesn't necessarily mean that the runtime will be the same. In fact, method 3 should be about 800 times faster than method 1 (https://towardsdatascience.com/how-to-make-your-pandas-loop-71-803-times-faster-805030df4f06)!

Another answer that may help you: Why is the constant always dropped from big O analysis?

bguest
  • 215
  • 1
  • 7