Finding $a_n$ with $a_n = o(n \cdot \log(n))$ and not $O(n)$

Question

Can you give me an example of a sequence $a_n$ ($n \in \mathbb N$) that satisfies the above conditions?

$o$ and $O$ are Landau symbols.

Answer 1

All you really need to do is find a sequence that is $o(\log(n))$ but not $O(1)$ and then multiply by $n$. The sequence $\log \log n$ is $o(\log(n))$ and unbounded, so $$ a_n = n \log (\log( n)) $$

Answer 2

There are a lot of functions that are not constant, but smaller than logarithm, for example:

• roots of logarithm $\sqrt{\log n}$, $\sqrt[3]{\log n}$, etc.
• double logarithm $\log \log n$, triple, etc.
• iterated logarithm $\log^* n$,
• inverse Ackermann function $\alpha(n)$,
• many, many others,
• combinations of the above.

Let $f(n)$ be such a function, then $nf(n)$ is a valid answer to your question.

I hope this helps $\ddot\smile$