1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
astraxan [27]
3 years ago
10

Assume you have a sorting algorithm that you can use as a black box. Use the sorting algorithm to sort the input list. Now write

an algorithm to count the number of duplicates again. Analyze the time complexity of your algorithm in the worst-case (ignore the time complexity of sorting). Could you improve the worst-case time complexity of your algorithm compared to the previous question
Computers and Technology
1 answer:
Ber [7]3 years ago
7 0

Answer:

Algorithm explained below

Explanation:

Algorithm to check duplicate when list of element is sorted:

CheckDuplicate( Sorted list )

    initialize count = 0

    Repeat untill we reach on end of list :

            if next is not end of list and current element is equal to next element

                    count = count+1

                    increase the pointer to next untill a different element is found

end CheckDuplicate

Worst Case Time Complexity will be O(n). Because there is only one iteration over the list will be performed.

Yes We have improved the worst case time complexity compared to previous question.

Actually after applying sorting all the similar element to will be next to each other.Then we will start iterating one by one from one side and check which is similar to next.If a different element will be find then we will check whether it's next is similar to it or not.

eg. 1 1 1 2 2 2 4 4 4 we can check duplicate in one iteration.

You might be interested in
Which of the following STEM discoverers is known as the “Prince of Math?”
Margarita [4]
The German mathematician & physicist ”Carl Friedrich Gauss”

Born: April 30, 1777, Brunswick, Germany
Died: February 23, 1855, Göttingen, Germany
8 0
3 years ago
A _____ is a type of legal protection for which person can apply to protect an invention or a discovery.
shepuryov [24]

Answer:

patent

Explanation:

A patent is an intellectual property, with this legal protection, we can exclude to use, sell, and importation of an invention for a limited period of years, but we must do an enabling public disclosure of the invention or discovery, it is a requirement of the patent law, a patent is considered an advantage in the industries world.

3 0
3 years ago
Where to buy a ps5<br> I really want one please help meh
lianna [129]

Answer:

You can buy one at gamestop, target, walmart, best buy and probably more stores

3 0
3 years ago
Read 2 more answers
Everyone say bye to brainly cause I’m reporting it for being against the law
PilotLPTM [1.2K]

Answer:   really

Explanation:

Opp

4 0
3 years ago
Read 2 more answers
Semiconductor memory is used mainly for primary storage even with its high cost. In another hand, the magnetic tape is the cheap
Charra [1.4K]
<span>Storage costs of magnetic tape are much lower than semiconductor storage (chip storage), but they take longer to access because they are not on-board the system and have to be added manually. Chip memory, on the other hand, can be used as primary storage for a system even with a higher cost because it's typically directly connected to the system board and is much more easily accessible by the system.</span>
8 0
3 years ago
Other questions:
  • Which tasks can a user accomplish by using the Find and Replace feature of Word? Check all that apply.
    11·1 answer
  • You notice that lately your computer has been running slow. When you open up your web browser, you get endless pop-up ads to the
    8·1 answer
  • What type of rain happens when cold air meets warm air
    14·1 answer
  • What does subscribing to a website’s RSS feed provide to a subscriber?
    10·1 answer
  • Which type of network attack uses a fake IP address to send data packets from an unauthorized user to a network?
    12·2 answers
  • Prevent a page break in the final paragraph of this document by keeping the lines together
    10·1 answer
  • i see tabs named mowed and Ramsey i tried shredding them and deleting them and ending all the processes but they start duplicati
    13·1 answer
  • Star and peer-to-peer are types of
    9·2 answers
  • Which term refers to the science that specifies the design and arrangement of items you use so you interact with the items effic
    15·1 answer
  • Which of the following is not considered essential for an electronic device to be called a computer?
    15·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!