What is the expected number of items looked at

Reference no: EM131824464

In computer science, it often occurs that items must be located within a list. How the items are stored in the list affects how long it takes to locate the items.

a) Suppose n items are stored in random order. To find a requested item, the items are searched sequentially until that item is found (assuming the requested item is on the list, of course). Let X be the number of items in the list that must be accessed (looked at) until the requested item is found. What is E(X)?

b) Suppose that 255 items are stored in a list in order and that we can access any element in the list. Now a binary search can be used to locate the requested item. We can look in the middle location, and if the item is not there, we will know if it is to the left or the right, etc. Now what is the expected number of items looked at? (Compare this with the result from part a) when n = 255.)

Reference no: EM131824464

Questions Cloud

Analyze the importance of network architecture to security : Analyze the importance of network architecture to security operations. Apply information security standards to real-world implementation.

What is the expected incremental cost : Reef Office Supplies is interested in estimating the cost involved in hiring new employees. What is the expected incremental cost

How does the media and use of video technology impact : How does the media and use of video technology impact the public's perception of police use of force?

How much can you withdraw each year during retirement : If you plan as if you will live forever and you wish to maintain constant annual purchasing power during retirement, how much can you withdraw each year during

What is the expected number of items looked at : Now what is the expected number of items looked at? (Compare this with the result from part a) when n = 255.)

Develop a reasonable retirement plan for the client : Develop a reasonable retirement plan for the client. Specifically, describe a well-reasoned savings plan that will meet the client's goals. In doing so

Which types of cars China imports : Let's think a little more about the Work It Out problem on the next page. If quality weren't held constant, what would you expect to happen to the additional.

Denote net winnings : Let X denote your net winnings (negative for losings) in a single play of this game. Determine E(X) and Var(X).

Identify suppliers and input for each process : Identify suppliers and input for each process. Identify outcomes and customers for each process. List key stages in each process.

User Account

All Pages