Incidentally this was difficult for me to understand. I think I get it but correct me if I don't.

1. For what size of problem is algorithm A faster an B

Algorithm A: 1000n³

Algorithm B: 2^n

Javanotes.com states "the larger the exponent, the greater the rate growth of the function. Exponential functions such as 2^n and 10^n, where the n is in the exponent, have a growth rate that is faster than that of any power function. In fact, exponential functions grow so quickly that an algorithm whose run time grows exponentially is almost certainly impractical even for relatively modest values of n, because the running time is just too long."

Note the following table;

Run Time n log(n) n*log(n) n squared n/log(n) 16 4 64 256 4.0
64 6 384
4096 10.7
256 8 2048 65536 32.0
1024 10 10240 1048576 102.4
1000000 20 19931568 10^11 50173.1 …show more content…
Now to the problem. "N refers to the size of the problem. The running time of n algorithm of O(f(n)) means that for large values of the problem size, n, the running time of the algorithm is no bigger than some constant times f(n). There is also a number C and a positive integer M such that whenever n is greater than M, the runtime is less than or equal to C*f(n)." So that means that the CPU and memory of a machine doesn't influence the answer you simply change the constants to a higher number. Therefore, because exponential functions 2^n have a growth rate higher than power functions 1000n³ I would say 1000n³ will always be faster than exponential