# Complexity of an algorithm with multiple inputs [duplicate]

This question already has an answer here:

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?

## marked as duplicate by Raphael♦Feb 26 '16 at 17:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• – 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

## 1 Answer

[If I have time, I'll answer the rest of the question later.]

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.

• I think this question is a duplicate; you may want to check if you can add something to the answers there. – Raphael Feb 26 '16 at 17:56