0

Let $a_i$ be a sequence of real numbers. If I know that $a_n = o(n)$ as $n \rightarrow \infty$, is it equivalent to say that:

$$\max_i^n a_i = o(n)$$

At first glance they seem different (the second seems stronger), but I think I am able to prove that they are the same:

Assume that $a_n = o(n)$:

Then, $\max a_i = \max \{a_1, a_2, ..., a_{n-j}, ..., a_n \} = \max \{c, o(n)\} = o(n)$

Now going the other way, assume $\max_i^n a_i = o(n)$:

$$a_n \leq \max^n_i a_i = o(n)$$

My question

Is my reasoning correct? Is there a more general statement hiding here?

Gary
  • 31,845
dmh
  • 2,958
  • 1
    What exactly does your second statement, $a\leq \max = \mathcal{o}(n)$ mean? Recall that "equality" in Bachmann–Landau notation does not denote true equality and is not generally a symmetric relation, so appending two such "equalities" is ambiguous. Are you stating that $a_n$ is also $\mathcal{o}(n)$ or just that $\max$ is? – Jam Oct 02 '22 at 16:27

1 Answers1

3

The first implication is true, the second has a counterexample:

$$a_n := \begin{cases} 1 & \text{if n is even} \\ -n & \text{if n is odd} \end{cases}$$

Traincopter
  • 105
  • 1
    ah ok good point, i should be careful with the signs. But i guess if we assume the sequence is positive then the two statements are equivalent – dmh Oct 02 '22 at 16:26
  • 1
    Actually also in that case it's not true, you can consider the sequence: $a_n := \begin{cases} n & \text{if n is even} \ 1 & \text{if n is odd} \end{cases}$

    in this case: $\lim_{n\to\infty} \frac{a_n}{n}$ doesn't exist, but $\lim_{n\to\infty} \frac{\max a_n}{n}$ does.

    By the way you asked about what it's called "superior limit", here you have a reference https://en.wikipedia.org/wiki/Limit_inferior_and_limit_superior

    For a sequence or a function having a superior or inferior limit is much weaker than having a proper limit. So it's often used if you don't know the limit exists.

     – Traincopter Oct 02 '22 at 17:37