3) What is the time complexity of the following code? for(int i=0 ; i=<n ; i++)
ID: 3589284 • Letter: 3
Question
3) What is the time complexity of the following code?
for(int i=0 ; i=<n ; i++)
{
a[i]=scan.nextInt();
}
for(int i=0 ; i<n ; 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?
Explanation / Answer
3)
For the code given let us understand the complexities of different statements.
for(int i=0 ; i=<n ; i++) // condition checked (n+1) times
{
a[i]=scan.nextInt(); // since this statement takes a constant time to run and runs for n times. Hence C(n)
} // where C is some constant time taken by this statement to run
for(int i=0 ; i<n ; i++) // again condition in for loop checked for (n+1)times
{
for(j=n ; j>= 0 ; j--) // runs (n+1) times for each value of i. so (n2 + n)
a[j]=a[j]+a[i] // runs for n times for each value of i. so (n2) times
}
Eliminating all the constants and taking the highest degree of n, we come to a conclusion that the time complexity of above code block is O(n2).
4)
a) In this case, since the array is not sorted, peforming a binary search will be foolish. As in binary search, the time interval is repeatedly divided in half, but needs the array to be sorted to work efficiently. So the sequential search will be better in this case.
b) Now that the array is sorted in this case we can deduce that:
(i) For Sequential Search, it would take 4 comparisons to find the value. starting from the first element to the 4th element.
(ii) For Binary search, it will take only 3 comparisons (first to compare the value with 67, dividing the array in half and searching again in first half; second to compare the value with 28, again resulting in the division of array and searching in the second sub-half; finally comparing with value 34).
5)
(a) A base case in a method body is a case for which the solution can be stated non-recursively. In simple words, the case for which the method leaves a recursion state is called as the base case.
In the given method, mystery(), we have two base cases which are as follows:
if( n <= 0 )
return 0;
else if( n == 1 )
return 1;
b)
(c) The output of the above program is:
1
0
4
Hope this helps...
BEST WISHES!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.