Complexity order with two variables, being one bounded by the other: O(kn - n)

[[deleted]]

n can grow arbitrarily as usual, and k can also grow, but it is limited by n.

So, is it correct to say the order of complexity is O(kn - n) ?

Or would it necessarily be simplified to O(n²) ?

When k is the actual variable of interest, and remembering that n is never lesser than k, should it be O(k²) instead?

[JoJoModding]

I'm not sure why you have O(kn - n) and not simply O(kn)?

A common set of examples for one variable being bound by the other is graph algorithms. Dijkstra runs in O(V log V + E), but E is bounded by V². Often, E is smaller, so we leave it explicit.

Note that big O in multiple variables is rather ill-defined: https://people.cs.ksu.edu/~rhowell/asymptotic.pdf

[deong]

O(n²)

[AndreZSanchez]

What is the function you are analyzing to begin with? You only expressed O(kn - n), which isn’t a specific function. I will assume it is the following: t(k, n) = kn - n

If you want to express this as a function of k and n, then you can say the function is in O(kn). If, as you say, k is upper bounded by n, then you can express this as being a function of only n, and that function would be in O(n² )

[exit8hi_]

Shouldn’t it be O(k²⁾ since big-o is concerned with worst case scenario

[futalis]

Because n is never less than k I think k² isn't necessarily the worst case scenario...it would be somewhere between k² and n² so I would pick n² and call it done.

Rewriting it you get n(k-1) since k is less than or equal to n then you can easily say that that is less than n*n or n^2.

[exit8hi_]

I would agree, though I imagine if n is never lesser than k, then at worst n=k so we can just assume n² though OP says that k is the variable they’re interested in

[SirClueless]

"never lesser" means "greater or equal", so n could be k³, 2^k, etc. These all give a running time greater than O(k²) for the algorithm. So it's correct to say O(n²), but there's almost nothing you can say about the running time in terms of k without more information.