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