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
mixas84 [53]
3 years ago
11

We have said that the average number of comparisons need to find a target value in an n-element list using sequential search is

slightly higher than n/2. In this problem, we find an exact expression for this average.
a. Suppose the list has an odd number of items,say 15. At what position is the middle item? Using sequential search, how many comparisons are required to find the middle item? Repeat this exercise with a few more odd numbers until you can do the following: If there are n items in the list and n is an odd number, write an expression for the number of comparisons required to find the middle item.
b. Suppose the list has an even number of items, say 16. At what position are the two "middle" items? Using sequential search, how many comparisons are required to find each of these? What are the average of these two numbers? Repeat this exercise with a few more even numbers until you can do the following: If there are n items in the list and n is an even number, write an expression for the number of comparisons required to find the two middle items.
c. Noting that half the items in a list fall before the midpoint and half after the midpoint, use your answer to parts a and b to write an exact expression for the average number of comparisons done using sequential search to find a target value that occurs in an n-element list.
Computers and Technology
1 answer:
bija089 [108]3 years ago
6 0

Answer:

Part a: If the list contains n elements (where n is odd) the middle term is at index (n-1)/2 and the number of comparisons are (n+1)/2.

Part b: If the list contains n elements (where n is even) the middle terms are  at index (n-2)/2 & n/2 and the number of comparisons are (n+2)/2.

Part c: The average number of comparisons for a list bearing n elements is 2n+3/4 comparisons.

Explanation:

Suppose the list is such that the starting index is 0.

Part a

If list has 15 elements, the middle item would be given at 7th index i.e.

there are 7 indices(0,1,2,3,4,5,6) below it and 7 indices(8,9,10,11,12,13,14) above it. It will have to run 8 comparisons  to find the middle term.

If list has 17 elements, the middle item would be given at 8th index i.e.

there are 8 indices(0,1,2,3,4,5,6,7) below it and 8 indices(9,10,11,12,13,14,15,16) above it.It will have to run 9 comparisons  to find the middle term.

If list has 21 elements, the middle item would be given at 10th index i.e.

there are 10 indices (0,1,2,3,4,5,6,7,8,9) below it and 10 indices (11,12,13,14,15,16,17,18,19,20) above it.It will have to run 11 comparisons  to find the middle term.

Now this indicates that if the list contains n elements (where n is odd) the middle term is at index (n-1)/2 and the number of comparisons are (n+1)/2.

Part b

If list has 16 elements, there are two middle terms as  one at would be at 7th index and the one at 8th index .There are 7 indices(0,1,2,3,4,5,6) below it and 7 indices(9,10,11,12,13,14,15) above it. It will have to run 9 comparisons  to find the middle terms.

If list has 18 elements, there are two middle terms as  one at would be at 8th index and the one at 9th index .There are 8 indices(0,1,2,3,4,5,6,7) below it and 8 indices(10,11,12,13,14,15,16,17) above it. It will have to run 10 comparisons  to find the middle terms.

If list has 20 elements, there are two middle terms as  one at would be at 9th index and the one at 10th index .There are 9 indices(0,1,2,3,4,5,6,7,8) below it and 9 indices(11,12,13,14,15,16,17,18,19) above it. It will have to run 11 comparisons  to find the middle terms.

Now this indicates that if the list contains n elements (where n is even) the middle terms are  at index (n-2)/2 & n/2 and the number of comparisons are (n+2)/2.

Part c

So the average number of comparisons is given as

((n+1)/2+(n+2)/2)/2=(2n+3)/4

So the average number of comparisons for a list bearing n elements is 2n+3/4 comparisons.

You might be interested in
A hard disk is a _ storage device
Leokris [45]

electro-mechanical data storage device

5 0
3 years ago
Read 2 more answers
What are the limits of hashing and verifying that files haven’t changed?
earnstyle [38]

The hashing function can take any number of key-value pairs and there is no specific limit to it.

<h3>What is hashing?</h3>

Hashing is a file-based algorithm for producing a fixed-length bit string value. A file is essentially a collection of data blocks. The length of the data is reduced by hashing to a fixed number or key that represents the original string.

When hashing is employed, the hash function may plot all of the keys and values to what the real size of the table is, demonstrating that the hashing function can take any number of key-value pairs with no restriction.

However, if the passwords are hashed in encryption, recovering the passwords is extremely difficult.

Thus, the hashing function can take any number of key-value pairs and there is no specific limit to it.

Learn more about the hashing here:

brainly.com/question/13106914

#SPJ1

5 0
2 years ago
Which of these is an advantage of having multiple layers in a drawing and enables you to make changes to one part of an image wi
Ivan

Answer:

enables you to make changes to one part of an image without accidentally changing other parts

Explanation:

Computer aided designs incorporate the use of multiple layers in drawings. The first layer is known as the layer 0, while the present layer the designer is working on is known as the current layer. The advantage of the incorporation of layers in designs include the following

1. It helps objects to be altered, grouped, hidden and moved as the designer wishes.

2. Layers can be grouped and worked on separated and common properties like color and line weight assigned to them.

3. Layers can be manipulated as the user wishes. They can be locked, frozen, turned off, etc.  Locking prevents accidental changes being made on objects.

4 0
2 years ago
Which devices are managed through device management?
Ratling [72]
Answer:
computers and Mobile phones ( including game consoles and tablets) are managed through device management
Explanation:
Device management includes a type of security software used to monitor,secure and manage systems such as mobile phones computer laptops and desktops, Tablets and smart televisions as well as Game consoles. It as well involves the management,operation and maintenance of the physical aspect of the systems from external threats/intruders
Anti virus software is an example of a device management software used to protect systems from malware, by detecting and removing them and also by preventing them.
Firewall is a complete device management tool because it detects and prevents intruders and virus from penetrating the system software
7 0
2 years ago
after clicking the start button on your computer screen desktop what option would you then select to examine systems components
xenn [34]
You would click on control panel to get to that area
7 0
3 years ago
Other questions:
  • Suppose you want to delete an existing file from within Word. What would you do? A. Click on the File button, choose Recent, ope
    9·1 answer
  • How many mustangs are built every day
    13·2 answers
  • Write a function called first_last that takes a single parameter, seq, a sequence. first_last should return a tuple of length 2,wh
    14·1 answer
  • IT investments can lead to developing IT capabilities and dynamic IT competencies, which can lead to achieving the following six
    5·1 answer
  • When a Python script is running as a standalone program, what will the __name__ variable be set to?
    7·1 answer
  • Sequential codes may be used to represent complex items or events involving two or more pieces of related data.
    7·1 answer
  • How many bytes does a common processor require to represent an integer?
    7·1 answer
  • A high school in a low-income area offers special programs to help students acquire the technical skills needed to find jobs as
    12·1 answer
  • when you sent email your email can be set to automatically keep a copy where do you find these copies​
    13·1 answer
  • PYTHON
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!