a.
If f(n) is O(g(n)) then
there exist a constant c > 0, and a constant
n0 such that for all n ≥ n0: f(n) ≤
c*g(n)
hence,
there exist a constant c > 0, and a constant
n0 such that for all n ≥ n0: g(n) ≥
(1/c)*f(n)
note that since c > 0, then the
constant (1/c) > 0
hence,
there exist a constant k > 0, namely k = (1/c), and
a constant n0 such that for all n ≥ n0: g(n)
≥ k*f(n)
which is the definition of g(n) = Ω (f(n)).
------------------------------------------------------------------------------------------------------------------------------------------------------------
b:
First of all we recall the definition of the big-Θ-notation:
Definition : f(n) ∈ O(g(n)) if ∀n ≥ n0, ∃0 < c1 ≤ c2 such that c1g(n) ≤ f(n) ≤ c2g(n)
If we state now the definition for both cases:
c1g(n) ≤ f(n) ≤ c2g(n) for Θ(g(n)) -------------------- (1)
c1αg(n) ≤ f(n) ≤ c2αg(n) for Θ(αg(n)) -------------------- (2)
As α > 0, redefining c1 and c2 as c˜1/2 = αc1/2 the we can rewrite (2) as:
c˜1g(n) ≤ f(n) ≤ c˜2g(n)
which complies with the inequality (1)
-------------------------------------------------------------------------------------------------------------------------------------------------------------
c:
We are required to prove that Θ(g(n)) = O(g(n)) ∩ Ω(g(n)). The proof is in two parts.
Part-1: First we prove that Θ(g(n)) ⊆ O(g(n)) ∩ Ω(g(n)):
f(n) ∈ Θ(g(n)) -------------------- (1)
∃c1, c2, n0 : ∀n > n0 : c1 g(n) ≤ f(n) ≤ c2 g(n) -------------------- (2)
∃c, n0 : ∀n > n0 : f(n) ≤ c g(n) -------------------- (3)
which, from the definition of O, tells us
f(n) ∈ O(g(n)) -------------------- (4)
∃c, n0 : ∀n > n0 : c g(n) ≤ f(n) -------------------- (5)
which, from the definition of Ω, tells us
f(n) ∈ Ω(g(n)) -------------------- (6)
f(n) ∈ O(g(n)) ∩ Ω(g(n)) -------------------- (7)
∀f : f(n) ∈ Θ(g(n)) =⇒ f(n) ∈ O(g(n)) ∩ Ω(g(n)) -------------------- (8)
This implies that Θ(g(n)) ⊆ O(g(n)) ∩ Ω(g(n)) -------------------- (9)
Part-2: Now you would need to do the same for the second (superset) part of the proof i.e., Θ(g(n)) ⊇ O(g(n)) ∩ Ω(g(n))
f(n) ∈ O(g(n)) [assumption] -------------------- (10)
f(n) ∈ Ω(g(n)) [assumption] -------------------- (11)
∃c1, n1 : ∀n > n1 : f(n) ≥ c1 g(n) [def. of Ω] -------------------- (12)
∃c2, n0 : ∀n > n0 : f(n) ≤ c2 g(n) [def. of O] -------------------- (13)
∃c1, c2, n0 : ∀n > max(n0, n1) : c1 g(n) ≤ f(n) ≤ c2 g(n) [combining (12) and (13) above] -------------------- (14)
f(n) ∈ Θ(g(n)) [def. of Θ and (10)] -------------------- (15)
Θ(g(n)) ⊇ O(g(n)) ∩ Ω(g(n)) [∀f : f ∈ O ∧ f ∈ Ω ⇒ f ∈ Θ] -------------------- (16)
Combining these subset (9) and superset (16) results, we get Θ(g(n)) = O(g(n)) ∩ Ω(g(n))
[ because A ⊆ B ∧ A ⊇ B ⇒ A = B ]
7. Prove the following assertions by using the definitions of the notations in- volved, or dispro...
1 Prove the following using the definitions of the notations, or disprove with a specific counterexample: Theta(g(n)) = O(g(n)) Ohm(g(n)) Theta(alpha g(n) = Theta(g(n)), alpha > 0 If f(n) O(g(n)), then g(n) Ohm(f(n)). For any two non-negative functions f(n) and g(n), either f(n) Ohm(g(n)), or f(n) < O(g(n))
Need help with 1,2,3 thank you. 1. Order of growth (20 points) Order the following functions according to their order of growth from the lowest to the highest. If you think that two functions are of the same order (Le f(n) E Θ(g(n))), put then in the same group. log(n!), n., log log n, logn, n log(n), n2 V, (1)!, 2", n!, 3", 21 2. Asymptotic Notation (20 points) For each pair of functions in the table below, deternme whether...
1) Consider the assertions below. Prove or disprove the assertion using limits, possibly with L’Hoˆpital’s rule. Also, if the assertion is true, show that it is true directly from the definition of the asymptotic notation and derive values for the relevant constants. (a) 3n^2 + 5n + 7 ∈ O(n^2) (b) 5(n − 2)! ∈ Θ(n!) (c) ∈ Θ(n) 2) Give the recurrence relation where indicated or solve the given recurrence relation by algebraically unrolling it. (a) Give a recurrence...
Suppose f(n) = O(s(n)), and g(n) = O(r(n)). All four functions are positive-valued and monotonically increasing. Prove (using the formal definitions of asymptotic notations) or disprove (by counterexample) each of the following claims: (a) f(n) − g(n) = O(s(n) − r(n)) (b) if s(n) = O(g(n)), then f(n) = O(r(n)) (c) if r(n) = O(s(n)), then g(n) = O(f(n)) (d) if s(n) + g(n) = O(f(n)), then f(n) = Θ(s(n))
Prove or disprove the following statements, using the relationship among typical growth-rate functions seen in class. a)n^15log n + n^9 is O(n^9 log n) b) 15^7n^5 + 5n^4 + 8000000n^2 + n is Θ(n^3) c) n^n is Ω (n!) d) 0.01n^9 + 800000n^7 is O(n^9) e) n^14 + 0.0000001n^5 is Ω(n^13) f) n! is O(3n)
Part I. (30 pts) (10 pts) Let fin) and g(n) be asymptotically positive functions. Prove or disprove each of the following statements T a、 f(n) + g(n)=0(max(f(n), g(n))) 1. b. f(n) = 0(g(n)) implies g(n) = Ω(f(n)) T rc. f(n)- o F d. f(n) o(f(n)) 0(f (n)) f(n)=6((f(n))2)
Formal Definitions of Big-Oh, Big-Theta and Big-Omega: 1. Use the formal definition of Big-Oh to prove that if f(n) is a decreasing function, then f(n) = 0(1). A decreasing function is one in which f(x1) f(r2) if and only if xi 5 r2. You may assume that f(n) is positive evervwhere Hint: drawing a picture might make the proof for this problem more obvious 2. Use the formal definition of Big-Oh to prove that if f(n) = 0(g(n)) and g(n)...
Subject: Algorithm solve only part 4 and 5 please. need urgent. 1 Part I Mathematical Tools and Definitions- 20 points, 4 points each 1. Compare f(n) 4n log n + n and g(n)-n-n. Is f E Ω(g),fe 0(g), or f E (9)? Prove your answer. 2. Draw the first 3 levels of a recursion tree for the recurrence T(n) 4T(+ n. How many levels does it have? Find a summation for the running time. (Extra Credit: Solve it) 3. Use...
Prove the following Green's identity for function..... 4. (a) Prove the following Green's identity for functions f.g E Co(2) where2C R'" where the notation : ▽ Vf n, where n is the outward pointing unit normal vector. You may use the divergence theorem, as well as the identity (b) Let G(x.xo) denote the Green's function for the Laplacian on Ω with Dirichlet boundary con- ditions, that is, 4,G(x, xo) = δ(x-xo), for x 62 (x,x;)= 0 for x Eon By...
Topology 3. Either prove or disprove each of the following statements: (a) If d and p map (X, d) X, then the identity topologically equivalent metrics (X, p) and its inverse are both continuous are two on (b) Any totally bounded metric space is compact. (c) The open interval (-r/2, n/2) is homeomorphic to R (d) If X and Y are homeomorphic metric spaces, then X is complete if and only if Y is complete (e) Let X and Y...