Determining Complexity You are given two vectors, A and B. A and B each has n en

Question

Determining Complexity

You are given two vectors, A and B. A and B each has n entries. You are assigned the task to develop and algorithm that does the following, in the order given. (You do not have to write this program.)

Determine the maximum and minimum of vectors A and B.

Sort each vector individually.

Assume a bubble sort that stops as soon as the vector is sorted.

Merge the two vectors in to a third vector, C.

Determine the maximum and minimum of vector C.

Determine the complexity, Big O (worst case) and Big ? (best case) of your algorithm. First find the complete function of n then use the highest-order term for the complexity. E.g., if you find worst case is

4n2 + 3n + 2, then show this as O(n2), however, you must derive the full function first. Hint: Consider loops.

Explanation / Answer

Solution:

We will consider the lines of the algorithm one by one and see how this goes

Determine the maximum and minimum of vectors A and B.

This will take O(n) + O(n) time for each

since the vectors are not sorted yet.

Sort each vector individually.

Assume a bubble sort that stops as soon as the vector is sorted.

Since we are sorting with the help of bubble sort so to sort the vector bubble sort will take O(n^2) for each

(we are considering worst case scenario)

Merge the two vectors in to a third vector, C.

Merging will take O(n) time

Determine the maximum and minimum of vector C.

This will take O(1) time since the Vectors are sorted now.

So the final expression will be

T(n)= 2n^2 + 2n + n + 1

Time complexity

T(n)= O(n^2)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.