Consider two vectors that are NOT sorted, each containing n comparable items. How long would it take to display all items (in an
1 answer:
Answer:
The correct answer to the following question will be "Θ(n2)
". 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:
=
And then the same manner compared again first with the second one, this takes.
=
Therefore the total complexity,
= Θ(n2)
You might be interested in
Answer:
The algorithm is as follows:
1. Start
2. Get the number of items (n)
3. Get the current price of the n items (a1, a2..... an)
4. Get the possible hiked price of the n items (b1, b2..... bn)
5. Calculate the difference between the current and hiked prices for each item i.e.
6. Sort the differences in descending order (i.e. from the greatest to the least)
7. Buy items in this order of difference
8. Stop
Explanation:
The algorithm is self-explanatory; however, what it does is that:
It takes a list of the current price of items (say list a)
E.g:
Then take a list of the hiked price of the items (say list b)
E.g:
Next, it calculates the difference (d) between corresponding prices
Sort the difference from greatest to lowest (as the difference is sorted, lists a and b are also sorted)
If there is no hike up to item k, the couple would have saved (i = 1 to d[k-1])
Assume k = 3
The couple would have saved for 2 item
The saved amount will then be added to the kth item in list a i.e. a[k](in this case k = 3) in order to buy b[k]
Using the assumed value of k
Add the saved amount (40) to a[3]
This new amount can then be used to buy b[3] i.e. 165, then they save the change for subsequent items