patternMinor
Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?
Viewed 0 times
whythesum_samedotsnot
Problem
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?
$$ \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?
Solution
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.
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.
Context
StackExchange Computer Science Q#113190, answer score: 8
Revisions (0)
No revisions yet.