EECS 340/454: Algorithms
Assignment 2: Asymptotic Notation
Problem 1
For the following statements, consider the functions f(n), g(n) and constant c such that f(n) ≥ 0,
g(n) ≥ 0, and c > 0. Indicate whether the statements are true or false. If true prove the statement
by providing a formal argument based on the definition of asymptotic notation, otherwise, provide
a counter-example to prove that they are false.
(a) max{f(n), g(n)} = Θ(f(n) + g(n)).
(b1) f(n) + c = O(f(n)).
(b2) If f(n) ≥ 1, then f(n) + c = O(f(n)).
(c1) If f(n) = O(g(n)), log(f(n)) ≥ 0 and log(g(n)) ≥ 0, then log(f(n)) = O(log(g(n))).
(c2) If f(n) = O(g(n)), log(f(n)) ≥ 0 and log(g(n)) ≥ 1, then log(f(n)) = O(log(g(n))).
(d1) f(2n) = Θ(f(n)).
(d2) If f(n) = O(n
c
), then f(2n) = O(n
c
).
(d3) If f(n) = Θ(n
c
), then f(2n) = Θ(f(n)).
Problem 2
Assume , a and b are constants such that 0 < < 1 < a < b. Sort the following functions
in asymptotically increasing order and indicate when two or more functions are asymptotically
equivalent (see definition below). Briefly justify your answers (no formal proof is needed).
n
n a
n
b
n
a
loga n
log(n
a
) log(n
b
) n/a
n (n + a)
b n
a+b
(n + b)
a
n
− n
−a n
a
log(n
)
log1/ n (log n)
a
log(bn) a
n
Definition. Two functions f(n) and g(n) are asymptotically equivalent if and only if f(n) = Θ(g(n)).
Example. Suppose we are sorting the following functions: n, log(n), 2n, 2
n
. Then, the asymptotical ordering is: log(n) n ≡ 2n 2
n
.
