Suppose you are given a list of n integers, each of size at most 100n. How many

Question

Suppose you are given a list of n integers, each of size at most 100n. How many operations would it take you to do the following tasks (in answering these questions, how many steps would it take: for example: log n, ?n, n, n2, n3, 2n, . . . steps. In other words, ignore multiplicative constants)

a) Determine if the number 2n + 7 is in the list.

I had this as just "n" steps. Test each n into 2n+7 and see if its on the list, at most would take n steps.

b) Determine if there are two numbers in the list whose sum is 2n + 7.

I had this as n^2 steps because we are testing nC2 subsets to check and see if the sum is 2n+7.

c) Determine if there are two numbers in the list whose product is 2n + 7 (This one is more subtle than it might appear! It may be to your advantage to sort the integers in the list).

Is this one also just n^2 steps? I don't see how its different from just checking the sum.

d) Determine if there is a number i for which all the numbers in the list are between i and i+2n+7.

Not sure about this one at all.

Explanation / Answer

a) Your idea is correct.

b) You can do it in nlogn steps as well. You should first sort the array . Now for each index i, you need to check whether therie is a j such that A[i] + A[j] = 2n+7. This means that for each i, you need to perform a binary search for the element 2n+7 - A[i]. Sicne each binary search takes logn steps, n binary searches take nlogn steps. Hence, the overall complexity is also nlogn (both sorting and n times binary search are nlogn complex)

c)It is indeed not different from checking for sum. You first sort the array. Then binary search for (2n+7)/A[i] for each i. This also takes nlogn complexity.

d) This is same as asking if A[i] >= min and A[i]+27 <= max.
When you multiply the 1st equation by -1 and add to the 2nd, you shall see that the question goes to max - min <= 2n + 7.
This can be easily done. min and max both can found in n steps, and difference of the numbers to be calculated in n steps and thus the entire process takes linear cpmplexity (order n steps).

Note that I have assumed that the basic operations (comparison, addition, subtraction, multiplication, division) take a constant amoint of time . If owever that is not the case, then the cmplexities would change

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.