# Questions tagged [summation]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
241 views

### Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?

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 ...
5k views

### Sum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n)

I wonder if there is a formula to calculate the sum of n/1 + n/2 + n/3 + n/4 + ... + 1. (Integer division) The number n can be as large as 10^12, so a formula or a ...
103 views

### Closed-form expression for the sums of the rows of the Trinomial triangle

There is a question in the second chapter of the book that I'm unable to solve, and unfortunately algorist.com does not provide a rigorous enough solution, or maybe I can't quite understand it. Here ...
625 views

### How to solve recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$

I have tried solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$ using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact ...
74 views

### How to parallelize a summation efficiently

Say I have an array a[1..n], and I want to output an array s[1..n] with s[i] = a[1]+...+a[i]. What is the best (or at least standard) way to do so in parallel? The way I can think of doing it, given m ...
463 views

### Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$
99 views

### Find the smallest group of numbers with sum bigger then $X$

Given a list of numbers $S$ where $0 < s_i < 100$, find the minimum sum group of numbers with a sum bigger than $X$. Each number can be used multiple times. Ex: for $S = [3,4.1], X = 10$ the ...
52 views

### Understanding a summation notation. Sum(j=2 to n) j - 1

I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs. I know how ...