[phoe-krk]

It shouldn't be called n because then `n log n` and `n log m` convey different meanings. In the first case, `n` is one and the same variable, where in the second, `n` and `m` are independent of each other.

You can call it `m` or `rho` or whatever, just use a different variable.

[ygra]

Here, ρ is not independent of n, though

[ehsankia]

It sort of is though. You can have a really large N with rho = 1, just like you can have a really small N with rho=N. They're orthogonal variables, and they both impact the run time.

[AstralStorm]

Rho is always 1 to n as defined.

In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.