0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Related: Time complexity based on two variables. $\endgroup$ – David Richerby Feb 26 '16 at 17:17
  • $\begingroup$ 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|$. $\endgroup$ – DylanSp Feb 26 '16 at 17:21
  • $\begingroup$ Short answer: (almost) nobody uses Landau notation with multiple variables in a well-defined, consistent way. Long answer: see duplicate, and here. $\endgroup$ – Raphael Feb 26 '16 at 17:56
  • $\begingroup$ If there are "several inputs", the sane way is to use the total size of inputs. $\endgroup$ – vonbrand Feb 26 '16 at 18:21
  • $\begingroup$ @vonbrand The whole field of parameterized complexity disputes that claim. $\endgroup$ – David Richerby Feb 26 '16 at 22:17
3
$\begingroup$

[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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.