Description
1. [30 points] Give the asymptotic complexity of each of the following functions in simplest terms. Your
solution should have the form Θ(n
α) or Θ((logµ
(n))β
) or Θ(n
α(logµ
(n))β
) or Θ(γ
δn) or Θ(1) where
α, β, γ, δ, µ are constants. (No need to give any justification or proof.)
(a) fa(n) = log2
(3n+2 + 5n
3 + 1);
(b) fb(n) = n
0.1 × lg(4n
5 − 3n
3
) + 3n
0.2
;
(c) fc(n) = 3 log4
(4n + 1) × log3 n + log2
(6n
2 + 8n);
(d) fd(n) = 613 + 26 × 7 log4
(62);
(e) fe(n) = 2(n + 4) log3
(2n
3 + 1) + 5n +
√
2n;
(f) ff (n) = 15n − 10n + n
100;
(g) fg(n) = 8
√
n + 2n;
(h) fh(n) = 3 × 5
n+9 + 6 × 3
n+9;
(i) fi(n) = √
2n3 + 3n2;
(j) fj (n) = 9 × 2
log2
(n
2+2n)
;
(k) fk(n) = (3 log4
(n
2 + 8) + 6√
n) × (log5 n + 4 log3 n);
(l) fl(n) = 34n + 43n;
(m) fm(n) = 5 log10(7n
3 − 6n + 9) + 9 log2
(5n
4.5 + 33n);
(n) fn(n) = (4n
3 + 2n
2 + 1) ∗ (n
2 + 5n + 13) ∗ (12n − 6);
(o) fo(n) = log10(4n + 6n + 8n);
2. [20 points]Rank the following functions by order of growth: that is, find an arrangement g1, g2, . . . ,
of these functions such that either gi = O(gi+1) or gi = Θ(gi+1), for any two consecutive functions
gi and gi+1 in your ordered list. (For example, given n, 2, 2
n, 3n +
√
n, your answer will look like:
2 = O(n), n = Θ(3n +
√
n), and 3n +
√
n = O(2n). ) You need to make your answer as tight as possible, that is, you should say gi = Θ(gi+1) whenever possible. In what follows, lg refers to log2 and ln refers loge where e is the natural number. (No need to provide justificaiton and proof for your answers.)
n lg n, 2
n+9
,
p
2n2 lg n + 3n, 2
lg n
, lg(n!), n√
ln n, 5
900
,
1
2
· 2
n
, 2 · 3
n
, n · 2
n
,
n
0.7
, lg(6n + 7) × lg(5n
0.3 + 21),
p
n3 − 2n2, 3
2n
, log6
((2n + 4)(3n + 2)(5n + 6)), 2
ln n
.
3. [10 points]Specify whether each of the following statement is true or false. If it is true, prove it. If it
is false, disprove it by providing a counter example. (All functions below are positive functions.)
(a) If f(n) = O(g(n)), then f
2
(n) = O(g
2
(n)) (where f
2
(n) = f(n) ∗ f(n) and g
2
(n) = g(n) ∗ g(n)).
(b) f(n) + g(n) = Θ(min{f(n), g(n)}).
4. [10 points] Provide an example in each of the following case, and briefly justify your answer.
(a) Give an example of a function f(n) such that: f(n) ∈ O(
√
n) and f(n) ∈ Ω(log n) but f(n) 6∈
Θ(√
n) and f(n) 6∈ Θ(log n).
(b) Give an example of a function f(n) such that: f(n) ∈ O(
1
2
√
n log n) and f(n) ∈ Ω(100√
n) but
f(n) 6∈ Θ( 1
2
√
n log n) and f(n) 6∈ Θ(100√
n).
5. [5 points] Prove that 7√
3n5 − 9n3 + 2 ∈ Θ(n
2.5
).
1
