Sam Redway - 1 year ago 54
Python Question

# Big O with 2 variables which mulitply together

If I take the function:

``````def nested_multiplier(a, b):
"""
returns a*b
"""
count = 0
for i in range(a):
for j in range(b):
count += 1
return count
``````

It is fairly clear here that the complexity in terms of number of asignments is going to be a * b.

Fine so far so good.

So if I want to work out the Big O in terms of a I guess I have to consider that the function has O(n) because I must consider b as a constant value in this case?

And equally if I want the big O in terms of b it would be O(n) for the same reasons.

This seems to make sense but intuitively with a nested iteration block like this I expect an O(n^2), or some other exponential type value. And this makes perfect sense when you consider a and b in terms of having the same value (i.e. let a = 5 and let b = 5 there will be 25 assignments).

So what is the correct way to express the complexity of this function in Big O notation?