Really been struggling in this subject, can\'t wrap my head around anything at a
ID: 3705140 • Letter: R
Question
Really been struggling in this subject, can't wrap my head around anything at all.
If I could have some help with this first algorithm it would set me in the right direction.
If I could please get
- A brief description of the algorithm
- identify the basic operation
- best-case efficiency
- worst case efficiency
- average-case efficiency
- aggregate efficiency
- and the order of growth
Thanks, answers will help me alot.
ALGORITHM MaxMin2(A[0.. , MaValue, MinValue) // Finds the maximum and minimum numbers in an array // Input parameter: An array A of n numbers, where n 21 I/ Output parameters: The largest and smallest numbers in the given 5 Max Value ? A[0] Min Value ? A[0] for i? l to n-1 do array, MaxValue and MinValue, respectively if Al> MaxValue Marl alue ? A[i] else if AMExplanation / Answer
This Algorithm is finding the maximum and minimum element in an array
Algorithm description: first we are initializing variable minValue and maxValue to the first element and after that we are iterating from the second element to the last element and first we are compairing whether that element is greater than our current maxValue if it is indeed greater than we are assigning maxValue to that current element and if it is not greater then we are compairing that element to the minValue if it is lesser than minValue then we are assigning minValue to that element and after finishing the iterations we will have maximum value of that array in maxValue and minimum value of that array in minValue.
Time Complexity: WORST CASE: worst case situation will happen when the array will sorted in descending order how lets see with an example let the array be
10 9 8 7 6 5 initially minvalue=10 and maxvalue=10
all the remaining n-1 values will have 2 comparison why because first we will compare it with maxvalue which will always fail so we have to go to the else part so 2 comparison for remaining n-1 elements
total comparisons=1+2(n-1)
so time complexity=O(n)
BEST CASE: Similarly in best case array will be sorted in ascending order for eg
1 2 3 4 5 6 initially min=1 and max=1
in this situation we will never go in the else part and you can see that clearly because if condition will always succeed so n-1 elements will be compare only 1 time
total comparison=1+n-1=n
time complexity=O(n)
similarly u can guess the average case complexity where some element will be in ascending order some will be in descending order it will also come out to be O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.