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
Which is one is bigger 326 kb or 60,436 kb?
Nitella [24]

60,436 is larger.

A byte is a sequence of 8 bits (enough to represent one alphanumeric character) processed as a single unit of information. A single letter or character would use one byte of memory (8 bits), two characters would use two bytes (16 bits).

7 0
3 years ago
Read 2 more answers
In the classic experimental design, there are two groups: the _____ group and the _____ group.
Tju [1.3M]

Main Answer:In the classic experimental design, there are two groups: the <u>treatment group and the control group.</u>

<u>Sub heading:</u>

<u>Explain treatment group and control group?</u>

Explanation:

1.The treatment group also known as the experimental group receives the treatment that the researcher is evaluating.

2.the control group  on the other hand does not receive the treatment.

Reference link:

https://brainly.com

Hashtag:

#SPJ4

5 0
1 year ago
Write the definition of a function named printpoweroftwostars that receives a non-negative integer n and prints a line consistin
Aleksandr-060686 [28]
To accomplish this without using a loop,
we can use math on a string.

Example:
print("apple" * 8)

Output:
appleappleappleappleappleappleappleapple

In this example,
the multiplication by 8 actually creates 8 copies of the string.

So that's the type of logic we want to apply to our problem.

<span>def powersOfTwo(number):
if number >= 0:
return print("*" * 2**number)
else:
<span>return

Hmm I can't make indentations in this box,
so it's doesn't format correctly.
Hopefully you get the idea though.

We're taking the string containing an asterisk and copying it 2^(number) times.

Beyond that you will need to call the function below.
Test it with some different values.

powersOfTwo(4) should print 2^4 asterisks: ****************</span></span>
4 0
3 years ago
Which was the first computer brought in nepal?<br>​
Natasha_Volkova [10]

Answer:

the first conputer brought in nepal was IBM 1401

3 0
2 years ago
Read 2 more answers
List four classification of computer based on their size ​
anyanavicka [17]
There are different sizes like-mini computers, microcomputer, mainframe computer and super computer.
5 0
3 years ago
Other questions:
  • What udp port is used for i k e traffic from vpn client to server?
    14·1 answer
  • A security administrator wants to empty the DNS cache after a suspected attack that may have corrupted the DNS server. The serve
    9·2 answers
  • Your school computer library has a network that connects computers and devices within a few small rooms. what type of network do
    7·1 answer
  • The difference between a want and a need is a want is not necessary for survival. Things necessary for survival are known as ___
    6·1 answer
  • What’s good and bad about having social media?
    14·2 answers
  • Directions: On the line before each item, write ”I” if the substance is an electric insulator or “C” if the substance is an elec
    10·1 answer
  • The most important task in developing a new computer system/app is to: a) choose the most current technologies such as operating
    5·1 answer
  • Yo, my Lenovo laptop keeps showing this screen but I can't sign in, can someone help me?
    5·2 answers
  • Suppose we want to select between two prediction models M1 and M2. We have performed 10-fold cross validation on each. The error
    14·1 answer
  • Answer for 3.4.8 rectangle code HS
    9·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!