Question

1. (15 pts total) Prove or disprove each of the following claims, where f(n) and g(n) are functions on positive values.

(a) f(n) = O(g(n)) implies g(n) = Ω(f(n))

(b) f(n) = O(g(n)) implies 2^f(n) = O(2^g(n))

(c) f(n) = O((f(n))^2)

Answer #1

(a)Given f(n) = O(g(n))

So for constant c and n0, we know that

f(n) ≤ c*g(n) where n>n0

As c>0, this can be rewritten as:

g(n) ≥ f(n)/c where n>n0

Let c1 = c, So

g(n) ≥ c1*f(n) where n>n0

Hence proved.

(b)

Given f(n) = O(g(n))

So for constant c and n0, we know that

f(n) ≤ c*g(n) where n>n0

Making this

2^f(n) ≤ 2^(c*g(n)) where n>n0

Let c1 = 2^c, So

2^f(n) ≤ c1*(2^g(n)) where n>n0

(c) Let f(n) = 1/n

if f(n) = O((f(n))^2)

So for constant c and n0, it should be:

1/n ≤ c*(1/n)^2 for n>n0

But this is not possible for any value of c as

1/n ≥ (1/n)^2

Hence this statement is false.

21.2. Let f(n) and g(n) be functions from N→R. Prove or
disprove the following statements.
(a) f(n) = O(g(n)) implies g(n) = O(f(n)).
(c) f(n)=?(g(n)) if and only if (n)=O(g(n)) and
g(n)=O(f(n)).

For each of the following pairs of functions f and g (both of
which map the naturals
N to the reals R), show that f is neither O(g) nor Ω(g). Prove
your answer is correct.
1. f(x) = cos(x) and g(x) = tan(x), where x is in
degrees.

For each of the following pairs of functions f and g (both of
which map the naturals N to the reals R), state whether f is O(g),
Ω(g), Θ(g) or “none of the above.” Prove your answer is correct. 1.
f(x) = 2 √ log n and g(x) = √ n. 2. f(x) = cos(x) and g(x) =
tan(x), where x is in degrees. 3. f(x) = log(x!) and g(x) = x log
x.

Prove or disprove: If f:A→B and g:B→A are functions and g◦f is a
bijection, then f and g are bijections.

Let f,g be positive real-valued functions. Use the definition
of big-O to prove: If f(n) is O(g(n)), then f2(n)+f4(n) is
O(g2(n)+g4(n)).

Prove or disprove the following statement: 2^(n+k) is an element
of O(2^n) for all constant integer values of k>0.

(a) Prove or disprove the statement (where n is an integer): If
3n + 2 is even, then n is even.
(b) Prove or disprove the statement: For irrational numbers x
and y, the product xy is irrational.

8. Prove or disprove the following statements about
primes:
(a) (3 Pts.) The sum of two primes is a prime number.
(b) (3 Pts.) If p and q are prime numbers both greater than 2,
then pq + 17 is a composite number.
(c) (3 Pts.) For every n, the number n2 ? n + 17 is always
prime.

Let N be a normal subgroup of G. Prove or disprove the following
assertion:
N and G/N have composition series ----> G has a composition
series.

Assume that f(n) = O(g(n)). Can g(n)
= O(f(n))? Are there cases where g(n) is
not O(f(n))? Prove your answers (give examples
for the possible cases as part of your proofs, and argue the result
is true for your example).

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 13 minutes ago

asked 18 minutes ago

asked 18 minutes ago

asked 22 minutes ago

asked 36 minutes ago

asked 48 minutes ago

asked 51 minutes ago

asked 52 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago