Questions tagged [summation]
The summation tag has no usage guidance.
13
questions
0
votes
1answer
28 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
1answer
46 views
Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true
2
votes
2answers
93 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 ...
0
votes
2answers
57 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 ...
4
votes
2answers
3k 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 ...
2
votes
0answers
59 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 ...
0
votes
0answers
54 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 ...
0
votes
3answers
81 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 ...
-1
votes
2answers
78 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+...
1
vote
1answer
342 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 ...
0
votes
1answer
62 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
2answers
346 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
2answers
235 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 ...
