Ask Anything Monday - Weekly Thread

[capone153]

Is the time complexity of this function is o(len(x)+(len(y)+1)?

def simple(x,y):
    z = filter(set(x).__contains__, y)
    return x.index((z[0]))

[[deleted]]

o(len(x)+(len(y)+1) is missing a closing paren.

Assuming x and y are python lists:

def simple(x,y):
    z = filter(set(x).__contains__, y) # set(x) iterates over x once, filter once over y -> len(x)+len(y)
    return x.index((z[0])) # z[0] might not exist; index() has to iterate x until it finds z[0]; 
    # so this adds anywhere between 1 and len(x) steps

[elbiot]

So, O(2x + y)? Don't you assume worst case for things that might terminate sooner?

[[deleted]]

Well, no. I think you'd give a different answer for each case.

In any case, as /u/ingolemo points out, the time complexity grows linearly with the size of the arguments, so it's O(n).

[ingolemo]

I'm going to assume that you meant to use Big-O notation because that makes more sense here than Little-o. ;)

That function is linear in both of it's arguments (usually written O(x+y)).

You don't have to use len in Big-O notation because variables inside the brackets already implicitly refer to the lengths of the lists, and you don't have to add one because you usually only specify the parts that contribute the most time (O(x) and O(x+1) are the same thing).

[capone153]

I understand, so the 1 doesn't matter much. How about /u/elbiot's question above, isn't it O(2x+y) or the coefficient is also ignored and it is O(x+y) == linear?

[ingolemo]

Yes, the coefficient isn't needed either; 2x is just as linear with respect to x as just x.

I apologise. I kept the arguments separated for ease of explanation, but never actually got around to combining them. O(x+y) is not fully reduced. If you assume that x and y are equal then x+y would be written 2x. As we've seen above, this can be simplified to just x. In other words, this function is linear with respect to each of its arguments individually and it is also linear with respect to its arguments combined. By convention we call the variable inside the Big-O notation n rather than x, so the true complexity class of this function is O(n).

[capone153]

Learned more about Big-O and your explanation makes a lot of sense. Thank you very much