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
erastovalidia [21]
3 years ago
12

Suppose that an algorithm uses only comparisons to find the i th smallest element in a set of n elements. Show that it can also

find the i 1 smaller elements and the n i larger elements without performing any additional comparisons
Computers and Technology
1 answer:
ELEN [110]3 years ago
4 0

Answer:

If the given algorithm employs m comparisons to determine 'x' that is the ith smallest element in a given sample of n elements. By tracing the m comparisons in the given log, the i -1 smaller elements can be determined by the theory of transitivity. Furthermore, If x > a and a > b, then x > b can be estimated without actually conducting a comparison between x and b. Similarly, the n - i larger elements can be found, too. It is uncertain that there is a possibility of x greater than a certain number or not by the comparison in the given log. It is not possible. Otherwise, the algorithm does not work correctly.

Explanation:

If the given algorithm employs m comparisons to determine 'x' that is the ith smallest element in a given sample of n elements. By tracing the m comparisons in the given log, the i -1 smaller elements can be determined by the theory of transitivity. It is uncertain that there is a possibility of x greater than a certain number or not by the comparison in the given log.

You might be interested in
Why did some people not like the arrival of machines?
Ahat [919]
People are concerned about losing their jobs. The industrial revolution introduced machines that removed the need for humans to be involved in highly repetitive tasks.
3 0
4 years ago
Which protocol below is used by email clients to send email
Alex17521 [72]
Did you forget the picture?
6 0
3 years ago
To create a cover letter to send to potential employers along with a resume, what software program should you use?
spayn [35]
Sending letters is easier when an individual is using an email. Emails are very easy to access, they can be sent twenty four / seven (24/7) and can also be received 24/7. Examples of email programs are yahoo and google websites.
3 0
3 years ago
) Suppose algorithm A takes 10 seconds to handle a data set of 1000 records. Suppose the algorithm A is of complexity O(n2). Ans
Mice21 [21]

Answer:

i) The time taken for 1500 records = 15 seconds.

ii) The time taken for 1500 records = 50 seconds.

Explanation:

A is an O(n) algorithm.

An algorithm with O(n) efficiency is described as a linearly increasing algorithm, this mean that the rate at which the input increases is linear to the time needed to compute that algorithm with n inputs.

From the question, it is given that for 1000 records, the time required is: 10 seconds.

Algorithm time taken is O(n)

Hence,

1) For 1,500 records

=> 10/1000 = x/1500

=> 10x1500/1000 = x

x = 15 seconds

Thus, the time taken for 1500 records = 15 seconds.

2) For 5,000 records

=> 10/1000 = x/5000

=> 10x5000/1000 = x

x = 50 seconds

Thus, the time taken for 1500 records = 50 seconds.

8 0
3 years ago
Complete the function to return the factorial of the parameter using recursion.
Klio2033 [76]

def recursiveFactorial(number):

   if number > 1:

       return number * recursiveFactorial(number-1)

   else:

       return 1

stringNum = input("Enter a positive integer: ")

num = int(stringNum)

print(recursiveFactorial(num))

7 0
3 years ago
Other questions:
  • What is the keyboard shortcut for the Undo command?
    8·1 answer
  • A new computer workstation has been installed in a small office. the user of the workstation can print a document using a networ
    9·1 answer
  • Which statement describes a disadvantage of e-government?
    9·1 answer
  • in access, entering the search criteria "B?" would yield which of the following results? a. bentonville b. be c. brimingham d. b
    14·1 answer
  • In attempts to improve their contribution to the environment, a company decided to adapt to green computing. Which of these tech
    15·1 answer
  • NAT is able to stop ________. Group of answer choices a) scanning probes sniffers from learning anything about the internal IP a
    8·2 answers
  • On the MarketingConsultants worksheet, in cells D10:H13, use a PMT function to calculate the end of the month payment amount. En
    15·1 answer
  • What is the importance of shape in graphic design?​
    5·2 answers
  • Answered
    10·1 answer
  • 1 point
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!