Big O Analysis with Multiple Variables

Question

I found this Big O analysis question and learned that you can have a Big O with more than one variable.

void f3(int n, int m, int r) {
        for (int i = 0; i < n; ++i) {                   O(N)
            for (int j = m; m > 0; m /= 2) {            O(log(M))   

            }
        }
    }
Answer: O(N log M)

Question 1 After reading Big O with 2 variables which multiply together, I am wondering if it is accurate to say that: it is only possible for there to be more than one variable in Big O only if there are multiple parameters.

I am unsure because Big O with multiple variables doesn't seem to be very common at-least from what I could find, most answers address the usual single variable Big O analysis.

Question 2 Should Big O with multiple variables be kept as they are or simplified based on whichever variable grows faster?

The best answer I could find was from Big O analysis for method with multiple parameters, where the answer basically says to leave each of the variables unless you can determine which variable grows fastest in which case you drop the other variables. I don't know how accurate the answer is though.

Answer 1

I am wondering if it is accurate to say that: it is only possible for there to be more than one variable in Big O only if there are multiple parameters.

No, that's not accurate. You can derive multiple variables from a single parameter. For example:

• a = the number of base 10 digits in n
• b = the number of 1 bits in the base 2 representation of n
• c = the greatest common divisor of n and m

Or, if there were a string parameter s:

• d = the length of s
• e = the number of words in s
• f = the number of lines in s
• g = the number of vowels in s

Should Big O with multiple variables be kept as they are or simplified based on whichever variable grows faster?

Sometimes you can simplify a multi-variable formula, but I wouldn't say you should do it. Don't think of multiple variables as something harmful to be avoided. If multiple variables better characterize the problem, or provide a tighter bound, or are easier to work with, then use multiple variables.

For instance, the cost of multiplying two matrices is dependent on the size of both. There are naturally multiple variables in play, and it'd be pointless to try to reduce their number. If I want to know how long it takes to compute the intersection of two sets, I need to know how many items are in each of them. A useful Big-O formula will have two variables, it's natural and unavoidable.