Question

Given a list of 1000 elements which of the following number is the largest?
A. The number of all possible subses of a given list
B. The number of all possible pairs of elemenst from a given list
C. The number of all possible permutations of a given list
D. 10,000,000,000,000,000

Answer 1

Given a list of 1000 elements which of the following number is the largest:

Explanation:

• Let's say there are n elements and let's convert the alternatives into easier mathematical expressions:
• A. 2^n
• B. (n choose 2) or (n^2-n)/2, or theta of n^2
• C. n!
• D. 10^16 < (2^4)^16 = 2^64
• For our n = 1000, clearly 2^1000 > 2^64, so A > D. Moreover, 1000^2 << 2^1000 since 2^1000 = (2^4)^250 > (10)^250 >> (1000)^50 >> 1000^2.
• Finally, we know that n! > 2^n asymptotically, but when? I actually looked it up and it's before n=4, so it's answer C.