3. You are satisfied with your computer program, but your manager complains that it is much too slow. You recall that in high school you realized that you only have to go up to about VN rather than all of the way up to N. (a) Assume that it takes unit time to add, subtract, multiply and divide integers. How fast is this new version of your algorithm, in order notation, as a function of N? (b) Assume that it takes linear time, i.e. e(n) time, to add, subtract, multiply, and divide two n-digit binary numbers. How fast is this new version your algorithm, in order notation, as a function of n (in the worst case)? (c) You are surprised when your manager complains that it is still much too slow. Is your manager right? Justify. 1 2. You recall an algorithm from elementary school for factoring a number N: Divide out all factors of 2, then of 3, then of 4, then of 5, then of 6, then of 7, etc. Finally, divide out all factors of N (of which there can be at most one). (a) Write pseudo-code for this algorithm (and print the prime factors). (b) Assume that it takes unit time to add, subtract, multiply, and divide integers. How fast is your algorithm, in order notation, as a function of N? (c) Normally we measure the time for such an algorithm as a function of the size of the input. In this case it is the number of digits in N, rather than the size of N. Assume that N is input as an n-digit binary number. How fast is your algorithm, in order notation, as a function of n? (d) If N is very large, you can no longer assume that arithmetic operations take constant time. Assume that it takes linear time, i.e. e(n) time, to add, subtract, multiply, and divide two n-digit binary numbers. How fast is your algorithm, in order notation, as a function of n (in the worst case)