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) Yes, it would take n steps, if the list is NOT sorted. If the list is sorted then it would take only log(n) steps by using binary search.

b) There is better solution and easy to implement: first sort the list (take n*log(n) steps), then iterate i from 0 to length(list)-1, perform binary search for number (2n + 7 - list[i]) in n-i-1 numbers on the right of list[i]. Iterate takes n steps, binary search takes log(n) steps, so overall you'll get n*log(n) steps. Plus n*log(n) steps from sorting the list before you'll get 2*n*log(n) ~ n*log(n) steps, which is significantly faster than n^2

c) The same as b) n*log(n), but binary search for number (2n + 7) / list[i] instead.

d) Find minimum value in the list, which takes n steps, find maximum value in the list, which also takes n steps. If (max - min) > 2n + 7 then there is no i. If (max - min) <= 2n + 7 then certainly i = min will satisfy the condition. So you just need to find max and min, which takes n steps (again, if the list is not sorted, but if it is sorted then it would take only 2 steps ~ 1 step if you ignore multiplicative constant)

(1 < log(n) << n < n log(n) << n^2 steps)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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