(32 Points) Problem 1.
Suppose you have algorithms with the running times listed below.
Assume these are the exact number of operations performed as a
function of the input size n.
Suppose you have a computer that can perform 1010
operations per second, and you need to compute results in at most
(8 Points) 1 hour
(8 Points) 1 week
(8 Points) 1 year (you can assume that 1 year = 365 days)
(8 Points) 1 century
For each of the algorithms, what is the largest input size n
for which you would be able to get the result within the given
That is, your solutions to this exercise should contain a table like
the one below together with explanations for each of the values you
provide in your table.
n(1/3) (= cubic root of n)
(40 Points) Problem 2.
In each of the following cases, determine whether
f(n) = O(g(n)), or
f(n) = Ω(g(n)), or
both (i.e., f(n) = Θ(g(n))), or
none of the above.
Prove your answers decisively, that is, provide a formal, mathematical
proof using either the definitions of O, Ω, and Θ; or the
theorems stated in class or in the textbook. (It is not enough just
to say for instance that "exponential grows faster than polynomial".)
n2 * log(n)
n2 * log(n)
(28 Points) Problem 3.
Construct a formal mathematical proof of each of the following two properties
using the definitions of O, Ω, and Θ.
(14 points) Transpose symmetry of O and Ω:
f(n) is O(g(n)) if and only if
g(n) is Ω(f(n)).
(14 points) Symmetry of Θ:
f(n) is Θ(g(n)) if and only if
g(n) is Θ(f(n)).