Complexity of an algorithm with multiple inputs
[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&nbsp;$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.