Sam Redway Sam Redway - 28 days ago 5
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?

Answer

You can use two variables inside the O(n) notation. For example this graph complexity question uses both the number of vertices and edges for complexity analysis. In your case the answer will be O(a*b), or if you want it more n-like, you can use O(n*m).

Assuming b or a as a constant to use only one variable in O(n) notation is misleading for analysis. Always use every input that affects complexity.