4
$\begingroup$

The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:

$$ \sum_{i=1}^n O(i) $$

is not the same as (I'm not using DNE because the book explicitly says "is not the same as")

$$ O(1) + O(2) + \dots + O(n) $$

Why is this? How are we to explicitly represent the first summation if not with the second? As an extension of the previous question, how do we do asymptotic analysis on such a summation?

$\endgroup$

migrated from softwareengineering.stackexchange.com Aug 29 at 6:20

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • 2
    $\begingroup$ Because when you add Big-O notation smaller terms disappear. See this possible duplicate. $\endgroup$ – 1201ProgramAlarm Aug 29 at 1:17
6
$\begingroup$

The difference is IMHO well explained in that book, the part you are referring to says

The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears.

So this $$ \sum_{i=1}^n O(i) $$

means a placeholder for $$ \sum_{i=1}^n f(i), $$

where $f(i)$ is an anonymous function from the set $O(i)$ — but it is always the same function in all terms of the sum. However, in $O(1) + O(2) + \dots + O(n)$, each term represents a placeholder for a (potentially) different anonymous function $f_i$ from the set $O(i)$. Note the book also says, the latter has "no clear interpretation", so it is quite meaningless.

$\endgroup$
6
$\begingroup$

Doc Brown answered your first question perfectly. Let me answer your second question. The expression $O(i)$ is a placeholder for a function which is bounded by $Ci$ for some $C > 0$. Therefore $$ \sum_{i=1}^n O(i) \leq C \sum_{i=1}^n i = C \frac{n(n+1)}{2} = O(n^2). $$ Furthermore, this bound is tight, in the sense that $n^2$ cannot be replaced with any asymptotically smaller function. This is because $i = O(i)$, and $\sum_{i=1}^n i = \Theta(n^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy