> lowering the upper bound to (log n) times (log log n)^3 — equivalent to (log n)^(1.000...1)
This is true! One of the things I find cool about big-O complexity using polynomial reference classes is that logarithms give you an infinitesimal value. Take that, "infinitesimals don't really exist" people!
I don't really understand what you're asking for. You can easily just verify the claim for yourself.
The limit as x goes to infinity of (ln x) / (x^k) is zero for all positive k. So if you want to approximate the behavior of a logarithm with a function of the form f(x) = x^k, k must be greater than 0 [because x^0 = o(ln x)], but less than every positive real number. This is the definition of an infinitesimal.
That's why it makes sense to say that x (log x)^3 is equivalent to x^{1.000000...[infinite 0s]...1}. Though in this analogy, it's more like x^{1.000000...3}.
>> Do you have a reference where I can learn about this?
> I don't really understand what you're asking for.
That comes across as rude and condescending; please don't communicate like that. Your English skills seem OK but in case you still need help, they're asking for a "reference" -- that's an online source of some sort probably, where they can "learn about" it -- that means that the reference would contain content helping them to understand the topic better. For example, the helpful content you gave after your rude and condescending initial comment would be an example of such content.
Only believing things that you can easily reason through if you are presented with some external authority really is a cognitive antipattern though.
I’d say that prologue was more medicinal than condescending. It’s good to remind people in the age of LLMs and ubiquitous search that “you can just think things.”
This is true! One of the things I find cool about big-O complexity using polynomial reference classes is that logarithms give you an infinitesimal value. Take that, "infinitesimals don't really exist" people!