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

  Cross-cultural opportunities and conflicts in canada

Short Paper on Cross-cultural Opportunities and Conflicts in Canada.

  Sociology theory questions

Sociology are very fundamental in nature. Role strain and role constraint speak about the duties and responsibilities of the roles of people in society or in a group. A short theory about Darwin and Moths is also answered.

  A book review on unfaithful angels

This review will help the reader understand the social work profession through different concepts giving the glimpse of why the social work profession might have drifted away from its original purpose of serving the poor.

  Disorder paper: schizophrenia

Schizophrenia does not really have just one single cause. It is a possibility that this disorder could be inherited but not all doctors are sure.

  Individual assignment: two models handout and rubric

Individual Assignment : Two Models Handout and Rubric,    This paper will allow you to understand and evaluate two vastly different organizational models and to effectively communicate their differences.

  Developing strategic intent for toyota

The following report includes the description about the organization, its strategies, industry analysis in which it operates and its position in the industry.

  Gasoline powered passenger vehicles

In this study, we examine how gasoline price volatility and income of the consumers impacts consumer's demand for gasoline.

  An aspect of poverty in canada

Economics thesis undergrad 4th year paper to write. it should be about 22 pages in length, literature review, economic analysis and then data or cost benefit analysis.

  Ngn customer satisfaction qos indicator for 3g services

The paper aims to highlight the global trends in countries and regions where 3G has already been introduced and propose an implementation plan to the telecom operators of developing countries.

  Prepare a power point presentation

Prepare the power point presentation for the case: Santa Fe Independent School District

  Information literacy is important in this environment

Information literacy is critically important in this contemporary environment

  Associative property of multiplication

Write a definition for associative property of multiplication.

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