Answer:
1. By assumption there exist N ∈ N and c ∈ R>0 such that for all n ∈ N with n ≥ N we
have
0 ≤ f(n) ≤ cg(n).
But then, since log2
is order-preserving:
log2 f(n) ≤ log2
cg(n)
= log2
c + log2
g(n).
That looks almost OK. We want to find a d ∈ R>0 such that log2 f(n) ≤ d log2
g(n).
Using the previous, it is sufficient to show:
log2
c + log2
g(n) ≤ d log2
g(n).
And this is OK, if:
log2
c
log2
g(n)
+ 1 ≤ d.
However, log2
g(n) might get closer and closer to 0 while n gets bigger. This leads us
to the following counterexample:
2(1 + 1
n
) ∈ O(1 + 1
n
),
but
log2 2 + log2
(1 + 1
n
) ∈/ O(log2
(1 + 1
n
)).
2. We have 2n ∈ O(n), however we saw last week that 22n ∈/ O(2n
).
3. By assumption there exist N ∈ N and c ∈ R>0 such that for all n ∈ N with n ≥ N we
have
0 ≤ f(n) ≤ cg(n).
But then, since squaring is order-preserving (on positive values), also:
0 = 02 ≤ f(n)
2 ≤ (cg(n))2
= c
2
g(n)
2
.
Thus f
2 ∈ O(g
2
).
