- Asymptotic analysis and orders of growth problems handout.
- Some notes on Little-ο and Little-ω.
Our reading question on this set was essentially:
Consider the following problem: Given a list of n integers, determine whether any subset of ____ of the integers sum to 42.
Now, with a brute force solution, does this take polynomial or exponential time?
The blank in that was filled with “three” for one section and with “any size” for the other section. For “three”, the answer is polynomial time because we can construct a triply nested loop to produce all sets of size three and check each one in constant time. (For “four”, it would be a quadruply nested loop.) For “any size”, the answer is exponential because there are 2n subsets of n elements.