# Help understanding the complexity of my algorithm (summation)

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).

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?

#### Solutions Collecting From Web of "Help understanding the complexity of my algorithm (summation)"

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}