Reference no: EM13167036
Binary search is much more efficient than linear search, with two caveats: (1) The list must already be sorted for binary search to work.
(2) For very short lists it's harder to say which algorithm is faster.
For this problem, you will quantify the performance difference
between the two. For this example, make the following assumptions:
1. We have an unsorted list of 256 items.
2. Sorting the list costs 4480 time units.
3. Each loop iteration of a linear search costs 1 time unit.
4. Each loop iteration of a binary search costs 4 time units.
If you only want to do one search in the list, it's clearly not worth sorting the list then running binary search, because the cost of
sorting is far higher than the cost of a single linear search.
How many searches for items that are not in the list would you have to do to make sorting and using binary search a better strategy than using linear search?
Also write down a few sentences to explain how you calculated your answer. Do not write any code!!!!
|
Write a program to produce a double table
: Using the ROL instruction to perform multiplication, write a program to produce a double table. This table should be built from a single int32 value provided by the user and print 3 rows beginning with the starting value. Within that row, the pattern..
|
|
Most cost-effective in terms of both time and money
: Search the Web for security education and training programs in your area. Keep a list and see which category has the most examples. See if you can determine the costs associated with each example. Which do think would be most cost-effective in terms ..
|
|
Write a program that will accept the names of 3 processes
: Write a program that will accept the names of 3 processes as command-line arguments. Each of these processes will run for as many seconds as: (PID%10)*2+3 and terminate.�
|
|
Random numbers
: Create a program that will generate a list of 200 random numbers (ranging from 1- 1000) and determine the medium, mode, and average of the list of numbers. Have the program display the original list and then display the list in ascending and desce..
|
|
Searches for items that are not in the list
: How many searches for items that are not in the list would you have to do to make sorting and using binary search a better strategy than using linear search?
|
|
You are working for country club
: You are working for country club with thousands of members. You have been tasked with designing a database to keep track of the members and their guests.
|
|
What factors might an organization consider
: What factors might an organization consider when choosing to implement an AD-integrated DNS zone versus a traditional zone? Describe a scenario in which it would be preferable
|
|
Write a c++ program to sort a list of number using vectors
: Write a C++ program to sort a list of number using vectors. Output the values when the elements are inserted into its correct position. Assume the first element in the list is sorted.
|
|
Write a script that uses two variables
: Write a script that uses two variables to store (1) the count of all of the products in the Products table and (2) the average list price for those products. If the product count is greater than or equal to
|