Reimplement method doSomething() so that it doesn’t modify the array. What is the cost of this new algorithm?

What will be an ideal response?

```
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

int j = 0;
// find the largest value in the range array[1] to array[n]
// that is not also in position k of the array.
for ( int i = 1; i < n; i++ )
if ( array[i] > array[j] && i != k )
j = i;
// postcondition: array[j] is the SECOND largest value in array
return array[j];
}


```
The solution introduces a new variable to loop through the second time looking for the second largest value. The comments reflect this change.

The cost is the same: O(n)