How to say a sequence is of $\mathcal O(k^3)$ I am wondering which one of the following statements are a more standard way of saying a sequence has cubic growth rate:


*

*The sequence $\lambda_k$ has cubic growth rate. 

*The growth rate of the sequence $\lambda_k$ is of cubic order. 

*The growth rate of the sequence $\lambda_k$ is cubic. 

*The sequence $\lambda_k$ is of order $\Theta(k^3)$.
 A: 
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.
