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
I'll give brainlist to right answers
xeze [42]
I think it’s number 1. Check the answer first.
5 0
3 years ago
From the computer desktop, clicking the Start button lets you _____.
stepan [7]
Locate and open Excel
8 0
3 years ago
Read 2 more answers
Step into the year 2028. How are people viewing digital video? Or have we moved on to a completely new format?
WINSTONCH [101]

In the year 2028 I don't believe our digital video viewing experience would change too much considering most, if not all, the population is already satisfied with how easy, simple, and versatile our current experience is. If everything changes one thing will for sure remain unchanged. That one thing is cinemas, I don't think cinemas will ever change much as they provide a constant source of revenue while providing a place for family and friends to get together to watch a movie before it becomes available to other sources.


8 0
3 years ago
In a(n) ____, the programmer uses a programming language (in context free grammar) to tell the computer what to accomplish and h
Mamont248 [21]

A 5GL fifth-generation languages a programming language design to solve given problem without programmer. The user only needs to solve the problem and condition without implementing an algorithm.

Explanation:

First Generation Language

The first generation language is called low- level style because they were used at a superficial level of abstraction. First-generation language referred to as the native language.

Second Generation Language

The second-generation language is also low-level language or assembly language. The second level of language uses the concept of mnemonics for the writing program. Symbolic name are used.

Third Generation Language

The third-generation language overcomes the first and second-generation languages. Third generation language is considered as high- level language because the target is to focus on the logic of the program.

Fourth Generation Language

The language of generation required a lot of time and effort that affect programmers.The fourth-generation was developed to reduce the time, cost, and effort.

Fifth Generation Language

The programming language of this generation focuses on constraints programming. The fifth-generation programming languages are Artificial Intelligence and Artificial Neural Network.

6 0
3 years ago
What icon might you see in device manager that indicates a problem with a device?
Nataly_w [17]
A yellow triangle with a exclamation mark might appear if a problem is detected with the device. Of course, this is different depending on the version of Windows you have.
7 0
3 years ago
Other questions:
  • Algorithm for arithmetic mean program
    13·1 answer
  • A(n) ______ is a type of collaborative website that allows users to create, add, modify, or delete website content.
    12·1 answer
  • What is the name of the interface that uses graphics as compared to a command-driven interface?
    11·1 answer
  • 14<br> Select the correct answer.<br> Which activity is a marketing technique?
    9·1 answer
  • Using the C language, write a function that accepts two parameters: a string of characters and a single character. The function
    11·1 answer
  • 11.
    9·2 answers
  • Porque sophia es un robot mujer?
    7·1 answer
  • Please help!! I need this asap! thank you so much!! &lt;3
    6·1 answer
  • D State Six Impact of ICT the society​
    7·1 answer
  • A program is required to three (3) numbers. calculate and print their total
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!