Question

For each of these, including procedure foo, give the best upper bound you can for the running time, using a simple function of smallest order. (E.g., it is correct to say the running time of each is O(n!n), but there are more slowly growing bounds available.)

a) O(n^2 )
b)O(nlogn)
c) O(n!)
d) O(2 n)

Answer 1

The best upper bounds for the running times are O(n^2), O(nlogn), O(n!), and O(2^n) respectively.

Step-by-step explanation:

a) For a function with a running time of O(n^2), the best upper bound is O(n^2) itself. This means that the running time of the function grows quadratically with the input size.

b) For a function with a running time of O(nlogn), the best upper bound is O(nlogn) itself. This means that the running time of the function grows in a linearithmic manner.

c) For a function with a running time of O(n!), the best upper bound is O(n!). This means that the running time of the function grows factorially with the input size.

d) For a function with a running time of O(2^n), the best upper bound is O(2^n) itself. This means that the running time of the function grows exponentially with the input size.