What does the following algorithm do? What is its time complexity?

Question

```
public static int doSomething( int array[], int n ) {
int k = 0;
// find the largest value in the range array[0] to array[n-1]
for ( int i = 1; i < n; i++ )
if ( array[i] > array[k] )
k = i;
// postcondition: array[k] is the largest value in array

// Swap the largest value with the value in position 0
int temp = array[0];
array[0] = array[k];
array[k] = temp;

k = 1;
// find the largest value in the range array[1] to array[n-1]
for ( int i = 2; i < n; i++ )
if ( array[i] > array[k] )
k = i;
// postcondition: array[k] is the SECOND largest value in array
return array[k];
}

```

Answer 1

As the bolded comments inserted in the code above describe, the method finds and returns the second smallest value in the array. It also modifies the array in that the largest element will be found in position 0.
Its time complexity is O(n).