Suppose the following pairs of functions f(n) and g(n) describe the number of operations that two...

Transcribed Image Text:

Suppose the following pairs of functions f(n) and g(n) describe the number of operations that two different algorithms would use to perform the same task. For each pair: (a) describe each function with a tight big-O bound that it uses only terms and constants appro- priate for big-O notation (for example, f(n) = 3n² +n becomes f(n) = 0(n²)); (b) tell us which function is more desirable for a running time from a big-O perspective (or if they are the same, say so); (c) Using the unsimplified formulas for both f(n) and g(n), calculate the amount of time it would take to perform the algorithm on n 10000 inputs, if each operation took 1/1,000,000,000 of a sec- ond. (That would be a processor with a speed of 1 Gigahertz, or a billion operations per second-in the ballpark of modern processors, but a little slow.) Give your answer in seconds unless it would take at least a day, in which case, give your answer in days. (There are 86,400 seconds in a day.) You can leave answers in scientific notation as long as they have the correct units (seconds or days). Note that the Google search bar's calculator can handle all computations necessary for this problem, if you lack a calculator that can handle the numbers. i. f(n) = n°/2 g(n) = 2n? %3D ii. f(n) = 1.01"/1000 g(n) = 1000n2 %3D iii. f(n) = 5n g(n) = 4n %3D %3D Suppose the following pairs of functions f(n) and g(n) describe the number of operations that two different algorithms would use to perform the same task. For each pair: (a) describe each function with a tight big-O bound that it uses only terms and constants appro- priate for big-O notation (for example, f(n) = 3n² +n becomes f(n) = 0(n²)); (b) tell us which function is more desirable for a running time from a big-O perspective (or if they are the same, say so); (c) Using the unsimplified formulas for both f(n) and g(n), calculate the amount of time it would take to perform the algorithm on n 10000 inputs, if each operation took 1/1,000,000,000 of a sec- ond. (That would be a processor with a speed of 1 Gigahertz, or a billion operations per second-in the ballpark of modern processors, but a little slow.) Give your answer in seconds unless it would take at least a day, in which case, give your answer in days. (There are 86,400 seconds in a day.) You can leave answers in scientific notation as long as they have the correct units (seconds or days). Note that the Google search bar's calculator can handle all computations necessary for this problem, if you lack a calculator that can handle the numbers. i. f(n) = n°/2 g(n) = 2n? %3D ii. f(n) = 1.01"/1000 g(n) = 1000n2 %3D iii. f(n) = 5n g(n) = 4n %3D %3D

Answer rating: 100% (QA)

Time taken number of operations time taken by 1 operation ie 11000000000 seconds 1 fn n ... View the full answer