assume n = 2^100. consider the following problem. given an unsorted list of size n you...

assume n = 2^100. consider the following problem. given an unsorted list of size n you can choose to sort it or not first. after this step, you get m queries q1, q2, ... qm. one by one of the form "is qi in the list?" Describe whether you would sort and what algorithm you would use if 1.) m= 10, and 2) m = 1000

Solutions

Expert Solution

1) Consider the case when the list is not sorted. Then each query will take n comparisons time to answer. Hence the time taken will be proportional to
.
If the list is sorted, then sorting alone will take time at least which is already more than the time taken to answer the queries without sorting.

Hence it is better not to sort the list for answering the queries.

2) Now, when the list is not sorted, the time taken will be proportional to .

If the list is sorted, say using Merge sort, then it will take time proportional to . After this, each query will take comparisons to answer, hence the total time taken by the queries is proportional to . The total time taken in this process is . This is clearly less than when the list was not sorted.

Therefore the list should be sorted, using mergesort.

Comment in case of any doubts.

venereology answered 2 months ago

Next > < Previous

Related Solutions

Given an unsorted integer array A of size n, develop an pseudocode with time complexity as...

Given an unsorted integer array A of size n, develop an pseudocode with time complexity as low as possible to find two indexes i and j such that A[i] + A[j] = 100. Indexes i and j may or may not be the same value.

Problem 1: Unsorted arrays Given an array of integers that is unsorted, implement the following functions:...

Problem 1: Unsorted arrays Given an array of integers that is unsorted, implement the following functions: • myAdd ( ): add an integer d to the array; return 0 if the operation is successful; return a negative number otherwise. • search ( ): given an integer d, if d is found in the array, return the index of the cell containing d. Return a negative number otherwise (e.g., d is not found in the array). • myRemove ( ): Step...

Given an unsorted array A of size N of integers, find a continuous sub-array which adds...

Given an unsorted array A of size N of integers, find a continuous sub-array which adds to the given number. Declare dynamic arrays and use only pointers syntax. (no [ ]'s or (ptr+1) stuff. input will be the number of input values to enter followed by the sum to compare with. print out the continuous sub-array of values that are equal to sum or the message 'no sum ofund.' there may be more than one sub-array to be found in...

Assume a population of 1,2 and 12. assume the sample size of size n = 2...

Assume a population of 1,2 and 12. assume the sample size of size n = 2 are randomly selected with replacement from the population. listed below are the nine different sample. complete parts a through d below 1,1 1,2 1,12, 2,1 2,2 2,12 12,1 12,2 12,12 a) find the value of the population standard deviation b) find the standard deviation of each of the nine samples the summarize the sampling distribution of the standard deviation in the format of a...

Create an unsorted LIST class. Each list should be able to store 100 names.

A random sample of size n = 100 is taken from a population of size N...

A random sample of size n = 100 is taken from a population of size N = 600 with a population proportion of p =0.46. Is it necessary to apply the finite population correction factor? Calculate the expected value and standard error of the sample proportion. What is the probability that the sample mean is less than .40?

Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements....

Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in...

7. Assume a population of 46, 51, 53, and 59. Assume that samples of size n=2...

7. Assume a population of 46, 51, 53, and 59. Assume that samples of size n=2 are randomly selected with replacement from the population. Listed below are the sixteen different samples. Complete parts (a) through (c). Sample x1 x2 1 46 46 2 46 51 3 46 53 4 46 59 5 51 46 6 51 51 7 51 53 8 51 59 9 53 46 10 53 51 11 53 53 12 53 59 13 59 46 14 59 ...

C++ Program 1–Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10...

C++ Program 1–Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill...

Assume a normal distribution of the form N(100, 100), answer the following questions: What proportion of...

Assume a normal distribution of the form N(100, 100), answer the following questions: What proportion of the distribution falls within 1 standard deviation of the mean (e.g., within -1 and 1 standard deviation)? What is the probability of a single draw from that distribution has a value greater than 115? What is the range that captures the middle 95% of the population distribution? If I randomly sample 10 observations from this distribution and calculate a mean, what is the probability...

Subjects