Big O: What is the name for the complexity O(a * b)?

user_18420669 0
Viewed 60

I am new to studying the Big O notation and have thought of this question. What is the name for the complexity O(a * b)? Is it linear complexity? polynomial? or something else. The code for the implementation is below.

function twoInputsMult(a, b) {
    for (let i = 0; i < a; i++) {
        for (let j = 0; j < b; j++) {
            // do something
        }
    }
}

Edit: According to the course I'm going through, it is not n^2 or quadratic since it uses two different numbers for the loops. Refer to the image below An image that says O(a*b) is not n^2

big-o time-complexity
1 Answers

O(ab) is just O(ab). Technically, ab is a multivariate polynomial of 2nd degree. But this is not equivalent to a quadratic polynomial, such as a2.

If you know more about a and b, you may be able to deduce more about their relationship. For instance, if a = O(b), then O(ab) = O(b2), which is quadratic. On the other hand, if a is a constant, then we can reduce it to O(b), which is linear.

Notice, by the way, that O(a + b) is just O(max(a, b)).

And if the real world interests you, I might also mention that both of these complexity classes show up a lot e.g. in graph theory, where we have the number of vertices |V| and the number of edges |E|, and typically |E| = O(|V|2) but not necessarily. For instance, Depth-first search has a time complexity of O(|V| + |E|), which just means that it is linear in terms of whichever there is more of: vertices or edges.

user_105591420
Related