# Questions tagged [summation]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
45 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 ...
49 views

### Asymptotic notation for summations

I am struggling to understand why this property of asymptotic notation is true
100 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 ...
63 views

### Summation and big theta

Can anyone suggest a starter book or website where I can find information and examples of putting functions under summation signs into Big Theta. basic Arihmetic , geometric, Quadratic are fine , but ...
4k 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 ...
73 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+...+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 ...
60 views

### Reconstructing an Array via Time-Intensive Subset Queries

I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem. I am given access to an ...
### 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 ...
The function: for (int i=1; i<n²; i++) for (int j=i; j<n; j++) print(j) Putting it into a relation, I got: $C1 + \sum_{i=1}^{n^2}(C2+... 1answer 569 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 ... 1answer 65 views ### Calculate the number of iterations in unusual nested loop I am trying to calculate the number of iterations of a sequence of nested loops of the form: \begin{equation} N = \sum_{j=0}^{j_T} \sum_{k=0}^{j} \sum_{l=0}^{k} \sum_{n=n_0}^{n_T} 1 \end{equation} ... 2answers 431 views ### Summation of asymptotic notation How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$ 2answers 240 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 ...