0

Imagine that I have:

$$\sum_{i = 1}^n O(n^{-1/2}) - \sum_{i = 1}^n O(n^{-1/2}).$$

By rewriting in the following way we could have

$$\sum_{i = 1}^n O(n^{-1/2}) - \sum_{i = 1}^n O(n^{-1/2}) = \sum_{i = 1}^n O(1)n^{-1/2} - \sum_{i = 1}^n O(1)n^{-1/2} = O(1) [\sum_{i = 1}^n n^{-1/2} - \sum_{i = 1}^n n^{-1/2}] = O(1) \sum_{i = 1}^n (n^{-1/2} - n^{-1/2}) = O(1) \cdot 0 = 0$$

However, by following many text books

$$\sum_{i = 1}^n O(n^{-1/2}) - \sum_{i = 1}^n O(n^{-1/2}) = O(\sqrt{n}) \neq 0$$

Therefore I am wondering which step in my development is wrong. Which one I am not allowed to do?

Eryna
  • 193
  • 2
    $\sum_{i = 1}^n O(1)n^{-1/2} - \sum_{i = 1}^n O(1)n^{-1/2} = O(1) [\sum_{i = 1}^n n^{-1/2} - \sum_{i = 1}^n n^{-1/2}]$ is wrong - $O(1)$ is not a single number – user8268 Apr 14 '23 at 10:06
  • 1
    Think about set $O(f)-O(f)$, does it contain it only $0$ function? – zkutch Apr 14 '23 at 10:09

0 Answers0