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
Erica has always selected large numbers of cells by clicking and dragging her mouse. A shortcut that she could use is to select
labwork [276]
D. enter because if you enter something on a cuputer or laptop your selecting something
5 0
3 years ago
Areas on which the development of the computer as a communication technology is based
Alchen [17]

Answer:

Artificial Intelligence.

Automated personal digital assistant.

THz frequencies for Communications (5G & 6G)

Blockchain.

Virtual reality and augmented reality.

Internet of Things (IoT)

Visible light communication.

LTE.

Explanation:

4 0
2 years ago
True/False: Each individual element of an array can be accessed by the array name and an element number, called a subscript. Tru
Dahasolnce [82]

Answer:

True

Explanation:

3 0
2 years ago
10. Question<br> What are the drawbacks of purchasing something online? Check all that apply.
max2010maxim [7]

Explanation:

1) the quality of purchased good may be low

2) there might me fraud and cheaters

3) it might be risky

4) we may not get our orders on time

7 0
2 years ago
A(n) _________ produces dynamic reports, supports alerts/rss functionality, and supports user subscriptions.
lesantik [10]

A(n) BI server produces dynamic reports, supports alerts/RSS functionality, and supports user subscriptions.

<h3>What exactly is BI server?</h3>

An on-premises report server with a web gateway, Power BI Report Server allows you to see and manage reports and KPIs. The tools for generating Power BI reports, paginated reports, mobile reports, and KPIs are also included. A business intelligence server created by Oracle is called Oracle Business Intelligence Enterprise Edition. It has sophisticated business intelligence capabilities that are based on a single architecture. The server offers centralized data access to all corporate entity-related business information.

There are five stages to query compilation in BI server:

  • Parsing
  • Create Logical Requests
  • Navigation
  • Code Generation Rewrite

To learn more about BI server , refer to:

brainly.com/question/7601044

#SPJ4

7 0
2 years ago
Other questions:
  • Name size of machine screw that is used to secure switches and receptacles to device boxes
    13·1 answer
  • Which of these is a preferred method for
    14·2 answers
  • A _____ is a machine that changes information from one form into another.
    7·1 answer
  • According to the author, there are five hedging strategies organizations can pursue. One of them is: Select one: a. commit with
    5·1 answer
  • Select the correct answer.
    6·1 answer
  • Which of the following should get a Page Quality (PQ) rating of Low or Lowest?
    5·1 answer
  • This is pixlr
    6·1 answer
  • Science Help
    11·1 answer
  • The advancement in speed of transportation is attributed to invention of this device
    8·1 answer
  • Which tab should a user click to access the Page Borders feature of Word?
    13·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!