Find both the minimum and the maximum in an array

Assignment Help Other Subject
Reference no: EM13539126

Min and Max

Suppose we wish to find both the minimum and maximum values in an array of n distinct elements.

To individually find either the minimum or maximum, there is clearly a n-1 lower bound on comparisons, since we must compare every element at least once. We can save a comparison by first scanning for the minimum, removing it, then scanning for the maximum. This takes a total of 2n-3 comparisons.

Based on this observation, prove the following statement true or false:

“It takes at least  2n-c comparisons, for some constant c , to find both the minimum and the maximum in an array of n distinct elements.”

Reference no: EM13539126

Questions Cloud

Calculate the overall efficiency of the system : A gas stream with a particulate loading of 20.0g/m^3 is passed through a 70%-efficient cyclone followed by a 95%-efficient ESP. Calculate the overall efficiency of the system.
The effect violent video games has on kids : The effect violent video games has on kids
Get the information from a community health survey : Get the information from a community health survey
The decryption algorithm : Using RSA, encode the word "cat" by encrypting each letter separately. Choose p=3, q=11 and e=9. Apply then the decryption algorithm. Show all the calculation steps.
Find both the minimum and the maximum in an array : To individually find either the minimum or maximum, there is clearly a n-1 lower bound on comparisons, since we must compare every element at least once.
Write a paper on the relative merits of .net and j2ee : Write a paper on the relative merits of .NET and J2EE as a platform for business systems integration.
Research a specific brand name secure usb thumb drive : Research a specific brand name secure USB Thumb drive and list the security advantages. Discuss its specifications. How does it compare with a cloud application of similar functionality? Name two of these services.
What would the value of the field containing the parity bit : What would the value of the field containing the parity bits be for the case of a two-dimensional parity scheme, if an even parity scheme is used? Your answer should use a minimum-length checksum field.
Why linux is installed on only a very small fraction of desk : 1) Describe some reasons why Linux is installed on only a very small fraction of desktop computers. Are there particular categories of products or users who might see Linux as more appealing than conventional operating systems? Do you think Li..

Reviews

Write a Review

Other Subject Questions & Answers

  Philosophers’ ideas-historical significance

Using the list of philosophers provided by your facilitator, select a quotation that best represents each of the philosophers. Explain why this quotation is an accurate representation of the philosophers’ ideas, historical significance, and key contr..

  Operational definitions and method procedures

Why is it essential that research studies include thorough operational definitions and method procedures? Why is generalization and replication in research so important?

  After viewing nutrition with john stossel

After viewing Nutrition with John Stossel, how do you think understanding how to read a food label might benefit you? How might you utilize this information to improve your eating habits?

  How does chile''s population growth rate

How does Chile's population growth rate compare to that of the United States?

  Psychologys recent history

Within psychologys recent history, ____________ psychology has been one of the stronger voices for a more positive approach to the study of human behavior.

  Openness to understanding a cultural difference

Contrast the dynamics between dominant cultures and subcultures either in a work setting or in society. Explain why it is important to understand the impact of culture. Give an example where you demonstrated your awareness and or openness to understa..

  Anthropogenic climate change-global warming

What is the evidence to date in support of and against the theory of anthropogenic climate change? Provide scientific support for your answer that is consistent with the geological record, which clearly shows that there have been many ice ages, and e..

  Consistent with the corporate strategy

Operating plans provide management with detailed implementation guidance, consistent with the corporate strategy, to help meet the corporate objectives. These operating plans can be developed for any time horizon, but many companies use a 5-year hori..

  Domestic work largely due to new technologies

In the United States and much of the Western world since World War II, women have actually seen an increase in domestic work largely due to new technologies.

  Imperative for clinicians and psychologists

As the baby-boomer generation gets older, it is imperative for clinicians and psychologists to be able to recognize pathological states that look like dementia, and others that do not.

  Summarize the biological basis of language acquisition

Summarize the biological basis of language acquisition. How does this information match your observations of a child learning to speak? How is language acquisition in children best supported?

  John stuart mill and karl marx view on political philosophy

What is John Stuart Mill and Karl Marx view on Political Philosophy and what are their views on "The Good Society"

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd