Question

Assume you have functions f and g such that f(n) is O(g(n)). For each of the following statements, decide whether you think it is true or false and give a proof or counterexample. a) f(n) 2 is O(g(n) 2 ) b) 2f(n) is O(2g(n) )

Answer 1

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

).