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?
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}