1. Suppose that algorithm A takes 1000n^3 steps and algorithm B takes 2^n steps (Note the carot symbol ^ means raise to the power of which we use here becuase we cannot create the appropriate mathematical symbol in moodle) for a problem of size n. For what size of problem is algorithm A faster than B (meaning algorithm A has fewer steps than B)? In your answer describe not only what the answer is but how you arrived at the answer.

2. Give the upper bound (big O notation) that you can for the following code fragment, as a function of the initial value of n.

for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++){ //do swap stuff, constant time } }

Do you think that the lower bound is likely to be the same as the answer you gave for the upper bound? In your response state why or why not.