Question

Consider two vectors that are NOT sorted, each containing n comparable items. How long would it take to display all items (in any order) which appear in either the first or second vector, but not in both, if you are only allowed LaTeX: \Theta\left(1\right)Θ ( 1 ) additional memory? Give the worst-case time complexity of the most efficient algorithm.

Answer 1

Answer:

The correct answer to the following question will be "Θ(​n​2​)

". The further explanation is given below.

Explanation:

If we're to show all the objects that exist from either the first as well as the second vector, though not all of them, so we'll have to cycle around the first vector, so we'll have to match all the objects with the second one.

So,

This one takes:

= $O(n^2)$

And then the same manner compared again first with the second one, this takes.

= $O(n^2)$

Therefore the total complexity,

= Θ(​n​2​)