This is an individual homework. No collaboration is allowed.
Submit a hardcopy of your written homework solutions by the
beginning of class (i.e., 1:00 pm) the day the homework is due.
Remember to show your work and explain your answers.
Correct answers without complete explanations won't receive full credit.
Incorrect answers with explanations may receive partial credit.
(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
time limit?
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.
1 hour
1 week
1 year
1 century
518n
n5
log10(n)
4n
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".)
f(n)
g(n)
1.(8 points)
n2 * log(n)
n2
2.(8 points)
n2 * log(n)
n3
3.(8 points)
3n
3(n+3)
4.(8 points)
33n
3n
5.(8 points)
n(1/2) (=sqrt(n))
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)).
