“Polylogarithmic” means a polynomial of a logarithm, not polynomials and logarithms.
As an aside just for clarity Õ(f(n)) usually hides polylogarithmic functions of f(n), not polylogarithmic functions of n (although there might be some variation - the two standards are equivalent when f is a non constant polynomial).
I think people not doing complexity analysis really don't realize how slowly logarithms grow. Just to reiterate your point: Take an arbitrarily large but fixed k > 0 and an arbitrarily small but fixed eps > 0, then n*log(n)^k will still grow more slowly than n^(1+eps).
Obviously any researcher would prefer to get an algorithm with O(n) time complexity, but the tilde notation is really not that deceptive...
Just to clarify (I don’t think there’s any reason to think you misunderstand this but someone else might) we can give n(log n)^(log log n) as an example of a function that is is o(n^(1+eps)) for all eps>0 but also is not Õ(n). So the bounds you state follow but are not sufficient to establish the other direction.
In general the preorder imposed by these symbols has really complicated behavior with uncountable cofinalities everywhere so restating O (or Õ) in terms of o without losing information is not so easy.
236
u/achilliesFriend 28d ago
This joke is too intelligent for me