Pseudocode/Java Mystery Algorithm

Question

I have an algorithm, and I want to figure it what it does. I'm sure some of you can just look at this and tell me what it does, but I've been looking at it for half an hour and I'm still not sure. It just gets messy when I try to play with it. What are your techniques for breaking down an algoritm like this? How do I analyze stuff like this and know whats going on?

My guess is its sorting the numbers from smallest to biggest, but I'm not too sure.

1. mystery(a1 , a2 , . . . an : array of real numbers)
    2. k = 1
    3. bk = a1
    4. for i = 2 to n
        5. c = 0
        6. for j = 1 to i − 1
            7. c = aj + c
        8. if (ai ≥ c)
            9. k = k + 1
           10. bk = ai
    11. return b1 , b2 , . . . , bk

Here's an equivalent I tried to write in Java, but I'm not sure if I translated properly:

public int[] foo(int[] a) {
        int k=1;
        int nSize=10;
        int[] b=new int[nSize];
        b[k]=a[1];
        for (int i=2;i<a.length;){
            int c=0;
            for (int j=1;j<i-1;)
                c=a[j]+c;
            if (a[i]>=c){
                k=k+1;
                b[k]=a[i];

Answer 1

Google never ceases to amaze, due on the 29th I take it? ;)

A Java translation is a good idea, once operational you'll be able to step through it to see exactly what the algorithm does if you're having problems visualizing it.

A few pointers: the psuedo code has arrays indexed 1 through n, Java's arrays are indexed 0 through length - 1. Your loops need to be modified to suit this. Also you've left the increments off your loops - i++, j++.

Making b magic constant sized isn't a good idea either - looking at the pseudo code we can see it's written to at most n - 1 times, so that would be a good starting point for its size. You can resize it to fit at the end.

Final tip, the algorithm's O(n²) timed. This is easy to determine - outer for loop runs n times, inner for loop n / 2 times, for total running time of (n * (n / 2)). The n * n dominates, which is what Big O is concerned with, making this an O(n²) algorithm.