7. Importance of algorithm efficiency (5 points)

This is a variation on problem 1-1 from the text (p. 14-15). Suppose you have a computer that can execute 2*10⁷ computational steps per second. If there are five algorithms with efficiencies O(lgn) [lgn = log of n to the base 2], O(square-root(n)), O(n), O(n²) and O(n³), and you need the algorithm to produce an answer in no more than one second, what is the range of input sizes from 1 to n for which each of these algorithms will be able to produce an answer in at most one second?

O(lgn) algorithm for input sizes 1 to _________

O(square-root(n)) algorithm for input sizes 1 to _________

O(n) algorithm for input sizes 1 to _________

O(n²) algorithm for input sizes 1 to _________

O(n³) algorithm for input sizes 1 to _________