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

Answer 1

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)