# Complexity of an algorithm with multiple inputs [duplicate]

I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$.

But what about when the complexity depends on several inputs? For example if an algorithm has complexity $O(n^2k)$, is it 'cubic', or maybe 'quadratic in $n$ and linear in $k$'?

I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?

• – David Richerby Feb 26 '16 at 17:17
• If you want to read up on some examples, look into graph algorithms. Those usually have runtime based on both the number of vertexes $|V|$ and the number of edges $|E|$. – DylanSp Feb 26 '16 at 17:21
• Short answer: (almost) nobody uses Landau notation with multiple variables in a well-defined, consistent way. Long answer: see duplicate, and here. – Raphael Feb 26 '16 at 17:56
• If there are "several inputs", the sane way is to use the total size of inputs. – vonbrand Feb 26 '16 at 18:21
• @vonbrand The whole field of parameterized complexity disputes that claim. – David Richerby Feb 26 '16 at 22:17

I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?
It's vague, unfortunately, and you should avoid writing anything like this, ever. It means at the very least, that the complexity depends somehow on $k^3$ and $n^3$ but I'm sure you'd already figured that out. Beyond that, it's impossible to say much. It's unclear whether it's some function of $k^3+n^3$ or some function of $k^3n^3$ or something else. It's also unclear whether they're talking about an upper bound or a lower bound: if I told you that a recipe needs a kilo of potatoes, you'd assume that was an upper bound, but if I told you that a restaurant needs kilos of potatoes, you'd assume a lower bound.