Intereting Posts

Periodic orbits of “even” perturbations of the differential system $x'=-y$, $y'=x$
Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$
Significance of starting the Fibonacci sequence with 0, 1…
Unique factorization domain that is not a Principal ideal domain
Concerning Roots of the cubic equation $f(x)=x^3+x^2-5x-1$ and the Greatest Integer (or Floor) function
Proving any product of four consecutive integers is one less than a perfect square
Discarding random variables in favor of a domain-less definition?
Calculate $\int_{0}^{1} (x-f(x))^{2016} dx$, given $f(f(x))=x$.
Proving the Möbius formula for cyclotomic polynomials
$PGL_2(q)$ acts on $\Omega$ $3-$transitively?
Is it possible to solve any Euclidean geometry problem using a computer?
The number of ways to order 26 alphabet letters, no two vowels occurring consecutively
Prime ideals in an arbitrary direct product of rings
Winning strategies in multidimensional tic-tac-toe
How are infinite-dimensional manifolds most commonly treated?

As an exercise, I wrote an algorithm for summing the all elements in an array that are less than i. Given input array A, it produces output array B, whereby B[i] = sum of all elements in A that are <= i.

A’s largest element is k.

My algorithm is as follows:

```
function summation(A, k)
Sorted = merge_sort(A)
j = 1
B[0] = 0
for i = 1 to k:
B[i] = B[i - 1]
while Sorted[j] <= i and j <= Sorted.length:
B[i] = B[i] + Sorted[j]
j++
```

Merge sort sorts in O(n log n). Now , intuitively I would say that the worst-case running time of the algorithm is n log n + k + n (since the inner while loop can only execute n times, regardless of k).

- Looking to understand the rationale for money denomination
- Algorithmic Analysis Simplified under Big O
- Santa is secretly deranged! or, how to hand-generate assignments for a gift exchange?
- Solving recurrences with boundary conditions
- Why is sorting pancakes NP hard?
- Minimum number of iterations in Newton's method to find a square root

However expressing this is a sum, I get n log n + k + n. i.e. expressing the for and while loop:

$\sum^k_{i=1}\sum^n_{j=1}1$ = $\sum^n_{i=1}n$ = $kn$

i.e. The algorithm’s runtime would be: n log n + kn

Any advice on where I am wrong?

- What is the difference between the Big O and Big O star (asterisk) operator?
- Asymptotic behavior of Harmonic-like series $\sum_{n=1}^{k} \psi(n) \psi'(n) - (\ln k)^2/2$ as $k \to \infty$
- An easy reference for genetic algorithm
- Examples of sub-exponential functions that aren't exponential functions when chained by a polynomial
- Twenty questions against a liar
- Parity of number of factors up to a bound?
- Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?
- Singular asymptotics of Gaussian integrals with periodic perturbations
- Showing that $\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$
- Understanding big O notation

Your sum expression is not wrong but it is a rather loose bound on the running time. In order to get the desired running time of $n \log n + k + n$ you could use the following sum

\begin{align}

\sum_{i=1}^k \, (1 + \text{number of items of size $i$})

\end{align}

since the inner loop is only executed while there are items of size $i$. You need the additional 1 for the assignment $B[i] = B[i-1]$ in the outer loop. The sum can be simplified to obtain the suggested running time of $n + k$ for the loops.

\begin{align}

\sum_{i=1}^k \, (1 + \text{number of items of size $i$})

= ~ & k + \sum_{i=1}^k \, (\text{number of items of size $i$}) \\

= ~ & k + n

\end{align}

- Prove that an annulus is not simply connected?
- totient function series diverges?
- Dependence of Axioms of Equivalence Relation?
- Class number/ quadratic field/divisibility-$2$
- Multiplicative Inverse of a Power Series
- Limits problem with trig? Factoring $\cos (A+B)$?
- How to tell if a Fibonacci number has an even or odd index
- Solve this with CBS: minimum value of $ 1/x + 4/y + 9/z $ with $x+y+z=1$
- Is $C^1$ with the norm $\left \| f \right \|_1=(\int_{a}^{b}\left | f(t) \right |dt)+(\int_{a}^{b}\left | f´(t) \right |dt)$ a complete space?
- How to prove the quotient rule?
- How to use stars and bars?
- Are all projection maps in a categorical product epic?
- Is the “$\mapsto$” notation considered “proper” mathematics?
- Number of permutations with repeated objects.
- Spectral Measures: Spectral Spaces (II)