Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

Questions tagged [summation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
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: ...
Jon Behnken's user avatar
0 votes
1 answer
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))$
Prikshet's user avatar
1 vote
0 answers
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: ...
adib's user avatar
  • 111
0 votes
0 answers
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 ...
Ninaaaaa's user avatar
-1 votes
1 answer
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 ...
reservoir's user avatar
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{...
chaaru's user avatar
  • 1
0 votes
2 answers
56 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}...
Lorem Ipsum's user avatar
3 votes
2 answers
302 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}^{...
Pavlo Maistrenko's user avatar
4 votes
1 answer
743 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 ...
Control's user avatar
  • 41
2 votes
1 answer
29 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 ...
postasguest's user avatar
1 vote
1 answer
63 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}$
Newbieee's user avatar
0 votes
1 answer
74 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 ...
asbestossupply's user avatar
0 votes
1 answer
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 ...
Edwards's user avatar
  • 103
0 votes
1 answer
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 ...
Vlad Mikheenko's user avatar
1 vote
1 answer
116 views

Asymptotic notation for summations

I am struggling to understand why this property of asymptotic notation is true
Cirrus86's user avatar
  • 123
2 votes
2 answers
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 ...
kasra's user avatar
  • 235
0 votes
2 answers
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 ...
david's user avatar
  • 19
4 votes
2 answers
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 ...
Loc Truong's user avatar
0 votes
2 answers
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 ...
Jon Anderson's user avatar
2 votes
0 answers
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 ...
H A Helfgott's user avatar
1 vote
0 answers
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 ...
SmeltQuake's user avatar
0 votes
3 answers
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 ...
Ilya Gazman's user avatar
-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+...
Ghost's user avatar
  • 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 ...
bingbong's user avatar
-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: \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} ...
user122011's user avatar
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). $$
mbhatti_20's user avatar
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 ...
user avatar