Determine the Big-O for the code below. For any arrays, assume they are of size n.

a) Determine the runtime for finding the index of the first occurrence of a target value in a list

public int find(int[] arr, int targ){

for(int index = 0; index < arr.length; index++){

if(target == arr[index]){ return index;}

}

return -1;

}

b) Determine the runtime of the selection sort algorithm

public void selectionSort(int[] arr){

for (int i = 0; i < arr.length - 1; i++)

{

int index = i;

for (int j = i + 1; j < arr.length; j++)

if (arr[j] < arr[index])

index = j;

int smallerNumber = arr[index];

arr[index] = arr[i];

arr[i] = smallerNumber;

}

return arr;

}

c) Determine the runtime of recursively computing the nth Fibonnaci number

public int fib(int n){

if(n > 1) return fib(n-1) + fib(n-2);

else if(n == 1) return 1;

else return 0;

}