Algorithm complexity

Question

I got this problem "Implement this method to return the sum of the two largest numbers in a given array."

I resolved it in this way:

 public static int sumOfTwoLargestElements(int[] a) {

     int firstLargest = largest(a, 0, a.length-1);

     int firstLarge =  a[firstLargest];
     a[firstLargest] = -1;

     int secondLargest = largest(a, 0, a.length-1);

     return firstLarge + a[secondLargest];
}

private static int largest(int s[], int start , int end){

    if (end - start == 0){

        return end;
    }


   int a = largest(s, start, start + (end-start)/2) ;
   int b = largest(s, start + (end-start)/2+1 , end);
    if(s[a] > s[b]) {

       return a;
    }else {

      return b;
    }

}

Explanation: I implemented a method 'largeset'. This method is responsible to get the largest number in a given array.

I call the method tow times in the same array. The first call will get the first largest number.I put it aside into variable and i replace it by '-1' number into the array. Then, i call the largest medhod second time.

Some one can tell me what is the complexity of this algo? please

You can find both numbers in the first pass and spare the second pass. It won't change the complexity but it'll run faster. :-) — assafmo
– assafmo, Commented Jul 12, 2013 at 18:42
+1 for the above comment. Also if it is just a list of numbers, then there are various other ways of solving the same... if you use an mechanism like count sort etc with negligible extra space and O(n) time complexity... — dharam
– dharam, Commented Jul 12, 2013 at 18:46
The real measure of complexity is that of future readers of this code, the time they spend figuring out how this works, when a much simpler algorithm will do the job. There is no clear benefit to recursion, or why two passes through the set are needed. And the algorithm is fundamentally broken (returns an incorrect result) when the two largest integers in the array are both less than -1. Accckkk! — spencer7593
– spencer7593, Commented Jul 12, 2013 at 19:16

amit · Accepted Answer · 2013-07-12 18:59:07Z

11

The time complexity of the algorithm is O(n).

Each recursive call's complexity is actually:

f(n) = 2*f(n/2) + CONST

It is easy to see (by induction¹) that f(n) <= CONST'*n - and thus it is O(n).

The space complexity is O(logN) - because this is the maximal depth of the recursion - so you allocate O(logN) memory on the call stack.

(1) If you use f(n) = 2*n*CONST - CONST you get:

f(n) = 2*f(n/2) + CONST = (h.i.) 2*(2*CONST*n/2 - CONST) + CONST =
=  2*n*CONST - 2CONST + CONST = 2*n*CONST - CONST

(Checking the base is is left as exercise for the reader)

edited Jul 12, 2013 at 18:59

answered Jul 12, 2013 at 18:37

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

michael_wu Over a year ago

So, f(0) has negative complexity? I rather think the complexity is O(2^n * log n).

amit Over a year ago

@undur_gongor The formula does not apply for the base or lower values, obviously (this is the point of induction, we prove from some point and up, all bets are off below it). The base should be for f(1), and as mentioned left as an exercise.

amit Over a year ago

@undur_gongor: And, to be exact - since we used only equality in the proof, we actually showed that the f(n) is in Theta(n) - so O(n) is a tight asymptotic bound.

spencer7593 · Accepted Answer · 2013-07-12 19:10:06Z

3

The complexity of the algorithm would be measured as O(n).

But the real answer is that your algorithm is WAY more complex, and more expensive in terms of machine resources than it needs to be. And it's WAY more expensive in terms of someone reading your code and figuring out what it's doing.

The complexity of your algorithm should really be on the order of:

public static int sumOfTwoLargestElements(int[] a) {

    //TODO handle case when argument is null,
    //TODO handle case when array has less than two non-null elements, etc.

    int firstLargest = Integer.MIN_VALUE;
    int secondLargest = Integer.MIN_VALUE;
    for (int v : a) {
        if ( v > firstLargest ) {
            secondLargest = firstLargest;
            firstLargest = v;
        } else if ( v > secondLargest ) secondLargest = v;
    }
    //TODO handle case when sum exceeds Integer.MAX_VALUE;
    return firstLargest + secondLargest;
}

edited Jul 12, 2013 at 19:10

answered Jul 12, 2013 at 18:51

spencer7593

109k15 gold badges122 silver badges148 bronze badges

1 Comment

Rhialto supports Monica Over a year ago

I think you'll need if ( v > firstLargest ) { secondLargest = firstLargest; firstLargest = v };

Fadhel Ghorbel · Accepted Answer · 2013-08-06 18:17:12Z

0

The reccurence for 'Largest' method is:

        _
f(n) = !
       !  1        n = 1
       !  2f(n/2)  n >=2 
       !_

If we experiment some few cases, we notice that 

f(n) = 2^log(n)   When n is power of 2       Rq:Log base 2

Proof:

By induction,

f(1) = 2^log(1) = 2^log(2^0) = 1

We suppose that f(n) = 2^log(n)=n

We show f(2n) = 2^log(2n)= 2n^log(2)=2n

f(2n) = 2*f(2n/2) = 2*f(n)
                  = 2*2^log(n)
                  = 2^log(n) + 1
                  = 2^log(n) + log(2^0)
                  = 2^log(2n)
                  = 2n^log(2)  by log properties
                  = 2n
Then f(n) = 2^log(n)=n  When n is power of2-smooth function f(2n) < c f(n). it follows smooth function properties that **f(n) = theta of n**

edited Aug 6, 2013 at 18:17

answered Aug 4, 2013 at 23:55

Fadhel Ghorbel

1311 silver badge11 bronze badges

Collectives™ on Stack Overflow

Algorithm complexity

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related