5 ms·
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 secon
by phoe-krk 8y ago
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 8y agoHere, ρ is not independent of n, though
- deleted 8y ago[deleted]
- AstralStorm 8y agoRho 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.
- ehsankia 8y agoIt 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.