Page BIT 42 Final Question 1 (20 points) the following questions: A. What is the
ID: 3846480 • Letter: P
Question
Page BIT 42 Final Question 1 (20 points) the following questions: A. What is the worst case running time for Bubblesort, in the "Big Oh" notation, assuming that your implementation is in no way optimized? B. What is the worst case running time for Binary Search in the "Big Oh" notation? C. Generally, Binary Search takes less time to run than Linear Search lin other words, Binary Search is faster). Describe a situation in which you would want to use Linear Search instead of Binary Search (even though Linear Search is slower) and explain why you would make this choice.Explanation / Answer
Question 1
Worst case running time of a bubble sort is O(n^2).
Following is a pseudo algorithm:
As, we can see the running time depends on how many times control enters the nested loops.
In the worst case or say any average case, it would have to go into for loop n times till its condition is false and this will be repeated n times until there is nothing left to swap(arrayis sorted). This gives us a total of n*n or n^2 executions of looping constructs. Hence running time for worst case in O(n^2).
B. Binary search is recursive. so, first Let T(n) be the time taken to the nth level,( here n is the input given )
T(n) = T(n/2) + O(1)
In binary search, at each level, we make a comparison with the midpoint that takes o(1) time, and then we compute a searching the value within n/2 values.
C. if data is unsorted, then the linear search will be faster then binary search, given that we only need to search it once. or the given list is too small
Post rest separately,
and if you understand it, do give it a thumbs up!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.