Suppose you are given a list of n integers each of size at m

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 we are interested primarily in whether take log n, , squareroot n, n, n^2, n^3, 2^n, steps. In other words, ignore multiplicative constants.) Determine if the number 2n + 7 is in the list. Determine if there are two numbers in the list whose sum is 2n + 7. 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 integer in the list). Determine if there is a number i for which all the numbers in the list are between i and i + 2n + 7. Determine the longest sequence of consecutive integers belonging to the list. Determine the number of primes in the list. Determine whether there are three integers x, y and z from the list so that x + y = z

Solution

(a) Number of operations it would take to determine if the number (2n+7) is in the list:

It would take at most n operations to determine if the number 2n+7 is in the list. If the list is already sorted, it may take less number of operations.

(b) Number of operations it would take to determine if there are two numbers in the list who sum up to 2n+7:

To do this, first we will be required to sort the list, which takes nln(n) operations. Secondly we will be reqiured to do a combined operation of iterating and searching. Iterating num1 from 0 to (size-1) and searching (for 2n+7-num1) will take n*ln(n) steps. The total operations required would be nln(n)+nln(n) = 2nln(n) which can be approximated as nln(n). Therefore, it will take nln(n) maximum operations to determine if there are two numbers in the list who sum up to 2n+7

(c) For product as well, we will be required to sort, iterate and search. Sorting will take nln(n) steps. Iterating from 0 to (size-1) will take n steps and then searching for (2n+7)/num1 will take ln(n) (since the list is already sorted). Therefore, combined operation of iterating and searching will take nln(n) steps and therefore, total number of operatioins required would be nln(n)+nln(n) = 2nln(n) which can be approximated by nln(n).