hello ,, how did we get this ansewr ?? \"how can we find the number of comparisi
ID: 3567493 • Letter: H
Question
hello ,, how did we get this ansewr ??
"how can we find the number of comparisions , number of assingnments and the asymptotic complexity ? "
Given the following java function: 2.1. Find the total number of comparisons performed in the statement number 5. Suppose that the length of the array data is n. The outer for loop runs n - 1 times The inner for loop runs n - i - 1 times So, the number of comparisons in statement 6 is 2.2. Find the total number of assignments performed in the line 6 in the best case and in the worst case. Suppose that swap is a function that accepts as parameters an array and the positions of two elements to be swapped. Best case: if the array is sorted in increasing order, 0 swap Worst case: if the array is sorted in decreasing order, there are swaps . 1.1. Find the asymptotic complexity in the worst case of the function bubbleSort. Total number of iterations: 2(n - 1)(2 + 3n) = O (n^2)Explanation / Answer
2.1 Clearly the outer loop runs for n-1 times .so the value of i varies from 0 to n-2 (n-1 values).Hence the total number of comparasions made in the line 6 is as shown.For each time of outer loop with i value the inner loop runs for n-i-1 time . hence summing over for the value of i =0 to i=n-2
2.2.
a) clearly if the array is in increasing order the if statement will always be false and hence no swap will be perfomed.
b) clealy acc to me ans is wrong . as the ans will be 1/3rd of the value given.I dont know why the factor of 3 is multiplied .but acc to me ans will be after removing the factor of 3 .As for each comparision we get one swap .Hence total no. of swap will be total number of comparasions made.
2.3)Forget everythiing and understand like this.The number of comparasions made =n(n-1)/2 .which is square in terms of n and there is no larger power of n then this one .Hence the asymptotic complexity will be of order o(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.