Question

Prove the additivity of big O notation:

f, g and h are functions of input size n. Prove that if $f \in \mathbb{O}(h)$ and $g \in \mathbb{O}(h)$, then $f+g \in \mathbb{O}(h)$

Answer #1

Your question text is not very clear and hence, I am providing the proof for additivity of big O notation.

Let f(n) = O(h(n)) and g(n) = O(h(n))

Since f(n) = O(h(n)), this implies that

0 <= f(n) <= c1 * h(n) where c1 is a positive constant ---------> 1

Since g(n) = O(h(n)), this implies that

0 <= g(n) <= c2 * h(n) where c2 is a positive constant ---------> 2

Adding 1 and 2, we get

0 <= f(n) + g(n) <= (c1 + c2) * h(n) where c1 + c2 is a positive constant

Hence, f(n) + g(n) = O(h(n))

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)).

(Note: "O" stands for Big O notation)
prove mathematically that if a Turing Machine runs in time
O(k(n)), then it runs in time O(h(k(n)) +c), for any constant c ≥ 0
and any functions k(n) and h(n) where h(n) ≥ n.

Find the big-O, big-Omega of the following functions (show steps
please)
a) f(n) = 5n^2 + 1
b) f(n)= (nlogn+1)*(n+1)

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)).

Prove mathematically that if a Turing Machine runs in time
O(g(n)), then it runs in time O(h(g(n))+c), for any constant c
>= 0 and any functions g(n) and h(n) where h(n) >= n.

True or False...Provide your reasons
If f(n) =o(g(n)), then f(n)=O(g(n))
If f(n) =O(g(n)), then f(n) ≤ g(n)
3. If 1<a=O(na), then
f(n)=O(nb)
4. A and B are two sorting algorithms. If A is O(n2)
and B is O(n), then for an input of X integers, B can sort it
faster than A.

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).

Fill in the following table, using Big-O notation to give the
worst and average-case times for each of the stack methods for a
stack of size N.
OPERATION
WORST-CASE TIME
AVERAGE-CASE TIME
constructor
empty
size
push
pop
peek

i) F o r t h e f o l l o w I n g f i n d t h e ( c o m p. E x
p.) f o u r I e r s e r i e s f o r x( t )
I I ) D r a w t h e am p &. P h a s e s p e c t r a
I I I ) T...

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)

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 4 minutes ago

asked 14 minutes ago

asked 19 minutes ago

asked 19 minutes ago

asked 22 minutes ago

asked 28 minutes ago

asked 31 minutes ago

asked 45 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago