How to say a sequence is of $\mathcal O(k^3)$

Question

I am wondering which one of the following statements are a more standard way of saying a sequence has cubic growth rate:

1. The sequence $\lambda_k$ has cubic growth rate.
2. The growth rate of the sequence $\lambda_k$ is of cubic order.
3. The growth rate of the sequence $\lambda_k$ is cubic.
4. The sequence $\lambda_k$ is of order $\Theta(k^3)$.

Answer 1

We write \begin{align*} \lambda_k= O(k^3)\qquad\qquad\qquad\qquad k\rightarrow \infty \end{align*} if the ratio $\lambda_k/k^3$ stays bounded as $k$ tends to $\infty$. In other words, there exists a $K\in\mathbb{N}$ and a constant $C>0$ such that \begin{align*} |\lambda_k|\leq C| k^3|\qquad\qquad\qquad\qquad k>K \end{align*}

We say that

• $\lambda_k$ is of order at most $k^3$ or

• $\lambda_k$ is big-Oh of $k^3$ (as $k$ tends to $\infty$)

This wording is stated in the classic Analytic Combinatorics by P. Flajolet and R. Sedgewick in Appendix $A.2$ Asymptotic notation together with the definition and correct wording of further asymptotic symbols.

• Note the big-Oh notation $O(k^3)$ is used whenever we want to state that a sequence $\lambda_k$ is bounded from above by a constant times $k^3$.

• We use another notation $\Omega(k^3)$ when we want to say that the sequence $\lambda_k$ is bounded from below by a constant times $k^3$. This means that the sequence $\lambda_k$ is of order at least $k^3$.

• If we can bound a sequence $\lambda_k$ from both sides, meaning it is both $O(k^3)$ as well as $\Omega(k^3)$ then we write $\lambda_k=\Theta(k^3)$ and say, $\lambda_k$ is order exactly $k^3$.

Conclusion:

• Point (1) to (3) do not precisely state that $\lambda_k$ is big-Oh of $k^3$ since the formulation bounded from above or an equivalent formulation is missing.

• Point (4) addresses with $\Theta(k^3)$ a different situation, namely $\lambda_k$ is both bounded from above as well as bounded from below by a constant times $k^3$.

Hint: Historical information around Big-Oh and friends is presented in Big Omega and Big Omicron and Big Theta (1976) by D.E. Knuth.