Questions tagged [summation]
The summation tag has no usage guidance.
23
questions
-1
votes
1
answer
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 ...
- 11
0
votes
0
answers
33
views
How to read and interpret these expressions?
I am reading a research paper in which following equation is given:
$\underset{\small{X}\\\text{s.t}\sum_{(i,k)\in \mathcal{A}}x_{ik}=1, \forall i\in \mathcal{M}}{\operatorname{max}} u$
where $\small{...
- 1
0
votes
2
answers
41
views
Big O of dynamic array
Skiena's Algorithm Design Manual, 3rd Ed p.71 gives the time complexity of a dynamic array according to the number of movements, $M$, as:
$$
M = n + \sum_{i=1}^{lg(n)} 2^{i-1} = 1 +2+ 4+\ldots+\frac{n}...
- 113
3
votes
2
answers
160
views
Linearity property of summation applied to Big Theta notation (CLRS math background appendix)
Section A.1 of the Mathematical Appendix of the CLRS, the third edition, page 1146, contains the following formula stating linearity property of summation applied to $\Theta$ notation:
$$
\sum_{k=1}^{...
4
votes
1
answer
512
views
Maximum sum of values in a square grid (one in each row/ column)
this is my first post here so bare with me :).
What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from ...
- 41
2
votes
1
answer
25
views
sum of Boolean characters larger degree
I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \{0,1\}^n$, then
$$
\frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{\langle S, x\rangle}=1
$$
if and ...
- 21
1
vote
1
answer
52
views
Is there a formula for this summation $\sum\limits_{k=i}^\mathbb{N}{i}$?
Is there a formulae for this summation?
I wonder this could be not a constant or to say that i * i?
$\sum\limits_{k=i}^\mathbb{N}{i}$
- 23
0
votes
1
answer
64
views
Factorial Formulae proof (from Algorithm Design Manual)
I'm going through Algorithm Design Manual and it didn't take long before I hit a proof I don't understand. Can anyone point me in the right direction?
From the book:
Problem: Prove that $\sum_{i=1}^n ...
- 103
0
votes
1
answer
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 ...
- 103
0
votes
1
answer
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 ...
0
votes
1
answer
88
views
Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true
- 113
2
votes
2
answers
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 ...
- 225
0
votes
2
answers
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 ...
- 19
4
votes
2
answers
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 ...
- 233
0
votes
2
answers
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 ...
- 11
2
votes
0
answers
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[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
0
votes
0
answers
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 ...
- 53
0
votes
3
answers
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 ...
- 899
-1
votes
2
answers
79
views
What would be the complexity for this relation?
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
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 ...
- 29
-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).
$$
- 11
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 ...
Padaca