# Questions tagged [summation]

The tag has no usage guidance.

27 questions
Filter by
Sorted by
Tagged with
27 views

### Why do we use summations when computing time complexity?

When we consider the time complexity of an algorithm, we use summations to represent loops. For instance, the following loop through an array of $n$ length: ...
• 101
253 views

### What is the simplified form of this big o

$O(\sum_{l=0}^{log_2n} l*2^l)$. I took the integral of the term which I think is $O(n*log(n))$
• 17
1 vote
40 views

### Grouping transactions having pre-determined sums?

I have a transaction grouping problem that I'm having trouble to devise the algorithm to solve it. Not even ChatGPT (version 3.5) can solve this correctly. Suppose I have five transactions: ...
• 111
23 views

### Time complexity summations

How to calculate the time complexity of a algorithm which contains while loops or if statements using summations? I only know how they work with the for loops. And I'm guessing the if loop are ...
40 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

27 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 ...
• 103
1k 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 ...
1 vote
116 views

### Asymptotic notation for summations

I am struggling to understand why this property of asymptotic notation is true
• 123
142 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 ...
• 235
196 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 ...
• 19
11k 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 ...
• 233
406 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 ...
345 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 ...
• 241
1 vote
67 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 ...
319 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 ...
• 909
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+... • 111 2 votes 1 answer 2k 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 ... • 29 -1 votes 1 answer 143 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: $$N = \sum_{j=0}^{j_T} \sum_{k=0}^{j} \sum_{l=0}^{k} \sum_{n=n_0}^{n_T} 1$$ ... 1 vote 2 answers 1k views ### Summation of asymptotic notation How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$ 6 votes 2 answers 314 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 ...