Determine the Big-O for the code below. For any arrays, assume they are of size
ID: 2247584 • Letter: D
Question
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;
}
Explanation / Answer
a) The run time complexity is O(n).
The for loop is running up to n to find the first occurence of the target.n comparisons are performed.
b) for each entry of i in the outer loop the inside loop runs for i+1 to n.
For i = 0 the inner loop runs for n-1
i = 1 the inner loop runs for n-2
So adding all values of i we get (n-1) + (n-2) + (n-3)...= ((n-1)(n))/2
= n^2/2 - n/2
Hence the complexity is O(n^2)
c) In this recursion we can see that time taken for nth fibonacci will be sum of time taken to calculate n-1th fibonacci and n-2th fibonacci.
We can write
T(n) = T(n-1) + T(n-2)
< T(n-1) + T(n-1)
< 2.T(n-1)
< 2.2.T(n-2)
< 2.2.2.T(n-3)
< 2^n T(0) T(00 = 1
< 2^n
So the complexity of this recursion will be O(2^n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.