3

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?

JB2
  • 269
  • Why is it $n\log{n} + k+n$ instead of $n\log{n}+kn$? The inner loop has to execute (at most) $n$ times for each of the $k$ runs through the outer loop. This gives the factor $kn$, not $k+n$. – Mankind Apr 20 '15 at 17:26
  • Doesn't the inner loop execute run $n$ times for each of the $k$ iterations of the outer loop? Hence $kn$ iterations of the inner loop in total? – Brian Tung Apr 20 '15 at 17:26
  • Incidentally, your $B[i] = B[i-1]$ assignment doesn't make sense. Why wouldn't you either (a) set $B[i]$ to $0$, or (b) only add $A[j]$ when $A[j]$ equals $i$, rather than is less than or equal to $i$? As it is, because $B[i]$ inherits its initial value from the final value of $B[i-1]$, an entry $A[j] = 1$ will be added $k$ times for $B[k]$, for instance. – Brian Tung Apr 20 '15 at 17:29
  • Also, you spend the time sorting $A$, but then don't appear to take advantage of it being sorted. (Not that this affects the computational complexity of your algorithm, but ...) – Brian Tung Apr 20 '15 at 17:31
  • @BrianTung: I set B[i] = B[i - 1] because j is the position of the last item that was summed at B[i - 1]. I then just need to add all the elements A that are less than i. – JB2 Apr 20 '15 at 17:48
  • @HowDoIMath: Because same reason than I gave above: j is the position of the last item that was summed at B[i - 1]. I don't do n iterations for each i. I do a maximum of n iterations in total (from i to k). – JB2 Apr 20 '15 at 17:49
  • @BrianTung: Sorry, yes, my mistake: I should have used Sorted, and not A. Updated the post. – JB2 Apr 20 '15 at 17:50
  • Ahh, I see. OK, so you do use the sort, good. I missed that. But then, in your complexity calculation, why are you multiplying the iteration counts? You're really only going through the array once, aren't you? – Brian Tung Apr 20 '15 at 17:52
  • Thanks - and, yup, exactly; I am only going through it once :) I guess hence my question. I think my problem is that I am how I can express the algorithm as a summation. – JB2 Apr 20 '15 at 18:04

1 Answers1

1

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}

philipph
  • 1,056