# Questions tagged [summation]

The tag has no usage guidance.

23 questions
Filter by
Sorted by
Tagged with
39 views

### Compute sum of moduli for a stream of integer numbers

We receive a stream of $n$ integer numbers: $x_1, x_2,\dots, x_n$. Assume that each $x_i$ is a constant and can be stored with $O(1)$ bits. Whenever a new number $x_i, i \geq 2$ is inputted, we need ...
33 views

24 views

### Efficiently Taking the Sums of all Pairs of Elements from a Set

I have a set of numbers and I want to find the sums of all possible pairs of elements. With the set $\{1, 2, 3\}$ for example, I would want $\{1+2, 1+3, 2+3\}$ as my answer. I could do that in n^2 ...
472 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 ...
88 views

### Asymptotic notation for summations

I am struggling to understand why this property of asymptotic notation is true
119 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 ...
156 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 ...
9k 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 ...
403 views

### Estimate the running time of a while-for-while loop

i, sq ← 1, 1 while sq < n for j ← 1 to sq k ← 1 while k ≤ j k ← 2 ∗ k i ← i + 1 sq ← i ∗ i I have expressed the running ...
150 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 ...
65 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 ...
265 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 ...
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+... 2 votes 1 answer 1k 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 ... -1 votes 1 answer 114 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} ... 1 vote 2 answers 961 views ### Summation of asymptotic notation How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$ 4 votes 2 answers 276 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 ... 