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 keyboard shortcut is a key or combination of keys that you press to access a feature or perform a command. ___________________
andrey2020 [161]
I believe that this is true.
Ctrl+F
Ctrl+C
Ctrl+V
These are all keyboard shortcuts.

8 0
3 years ago
You are installing windows on a new computer. Using the RAID controller on the motherboard, you configure three hard disks in a
Sergio [31]

Answer:

On the screen where you select the disk to install Windows, click "Load Driver"

Explanation:

While the user has Windows installed on a new system. Instead, he configures several hard disks in such a RAID 5 series using the RAID controller onto the motherboard. The user is left unpartitioned and improperly formatted in the list. He edits that boot request from either the optical drive for the BIOS to boot. He installs DVD drive, begins the configuration, and boots to the disk.

Then press the "Load Driver" button on the monitor where he picks the disk to install Windows

7 0
3 years ago
Class secretType { public: static int count; static int z; secretType(); secretType(int a); void print(); static void incrementY
ANEK [815]

Answer:

a. secretType mySecret(9)

Explanation:

6 0
3 years ago
Which of the following statements is most true? A user's online identities, actions, and relationships rarely have consequences
ale4655 [162]

Answer:

Online activities are increasingly used to make real-world decisions.

Explanation:

People use increasingly <em>world wide web</em>. They create profiles and communicate with others on social networks, share thoughts and moments of their life on online platforms.

These <em>online</em> activities become part of one's identity. Therefore these activities can give information about user's behaviors, attitudes, likes and dislikes.

All this data are being used to make real world decisions about a user or a group of users. For example, trough one's online check-ins, frequently used location of the users or can be determined. Similarly, trough social media likes or posts, one's hobbies can be predicted.

Therefore, social media and online presence in general, is not necessarily safe or private but important places which have valuable information of the users that can be used in real world.

8 0
3 years ago
Addictions may ______ friends and family
Airida [17]
C because alienation with addictions may block out friends and family.
6 0
3 years ago
Read 2 more answers
Other questions:
  • Universal Containers has implemented a strict software architecture for their custom Apex code. One of the requirements is that
    14·1 answer
  • Which device lets you hear audio on your computer?
    12·2 answers
  • Helppppppppppppppppppp
    11·1 answer
  • Find the area of the regular hexagon below by using the area formula for triangles.
    7·1 answer
  • Create a SavingsAccount class. Use a static data member annualInterestRate to store the annual interest rate for each of the sav
    10·1 answer
  • During a night flight, you observe a steady red light and a flashing red light ahead and at the same altitude. What is the gener
    11·1 answer
  • Please code this in c++
    10·1 answer
  • Ask the user for a total food bill and then find the new total after 6% tax and a tip of the users choice (15, 18, 20%) in pytho
    8·1 answer
  • Select the correct answer.
    10·1 answer
  • Microsoft recommends when that you create passwords with upper and lowercase letters, numbers, symbols, and use at least _______
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!