3) What is the time complexity of the following code?

for(int i=0 ; i=

{

a[i]=scan.nextInt();

} for(int i=0 ; i

for(j=n ; j>= 0 ; j--)

a[j]=a[j]+a[i]

}

4) Searching and sorting are two fundamental types of algorithms that we use in computing. Consider the following array. Suppose we need to find a number in the array given below int[] a ={100, 157, -2, 12, 67, 890, 28, 34, 156}

a) What is the best searching algorithm we can use (sequential or binary) in this situation? Explain your answer

b) Now consider that the array is sorted. Suppose you need to find number 34 in the array. int[] a ={-2, 12, 28, 34, 67, 100, 156, 157,890}

i.) Workout the sequential search and determine how many comparisons are needed if we use sequential search?

ii.) Workout the sequential search and determine how many comparisons are needed if we use binary search?

5. Recursion: Consider the following program

. public class RecursionMystery

{

public static int mystery(int n)

{ i

f( n <= 0 )

return 0;

else if( n == 1 )

return 1;

else return n + mystery( n - 2 ) ;

}

public static void main(String[] args)

{

System.out.println( mystery(1) ); //-------1

System.out.println( mystery(-6) ); //-------2

System.out.println( mystery(3) ); //-------3 }

}

//end of class

a) How many base cases are there in the recursive function mystery above? What are they?

b) Trace the execution of the function call in statement 3 above?

c) What is the output of the above program?