[Solved] CECS328 hw2

Click And Check all our Assignments
Click Here and Upload you Assignment for Free!

INSTANT DOWNLOAD!

100/100 Trustscore on scamadviser.com

10 USD $

Category: Tag:
  1. Prove that f(n) = 10 · n4 + 2 · n2 + 3 is O(n4), provide the appropriate C and k

f(n) = O(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

10 · n4 + 2 · n2 + 3 ≤ 10 · n4 + 2 · n4 + 3

≤ 10 · n4 + 2 · n4 + 3 · n4

= 15 · n4,n ≥ 1

Let c = 15 and k = 1 then the statement translates to

f(n) ≤ c · g(n),n k

By the definition of O notation f(n) = O(g(n))

  1. Prove that f(n) = 2·n2nlog2(n)+3·log2(n) is O(n2), provide the appropriate C and k constants.

f(n) = O(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

2 · n2 n · log2(n) + 3 · log2(n) ≤ 2 · n2 + n2 + 3 · log2(n)

≤ 2 · n2 + n2 + 3 · n2

= 6 · n2,n ≥ 1

Let c = 6 and k = 1, then the statement translates to

f(n) ≤ c · g(n),n k

which by the definition of O notation f(n) = O(g(n)).

  1. Prove that f(n) = 2·n4log2(n4)−n2+3·log2(n) is O(n4log2(n)), provide the appropriate C and k constants.

f(n) = O(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

2 · n4 · log2(n4) − n2 + 3 · log2(n) = 8 · n4 · log2(n) − n2 + 3 · log2(n)

≤ 8 · n4 · log2(n) + n4 · log2(n) + 3 · log2(n)

≤ 8 · n4 · log2(n) + n4 · log2(n) + 3 · n · log2(n)

= 12 · n4 · log2(n),n ≥ 1

Let c = 12 and k = 1 then the statement translates to

2 · n4 · log2(n4) − n2 + 3 · log2(n) ≤ c · n4 · log2(n),n ≥ 1

which by the definition O notation f(n) = O(g(n)).

  1. Prove or disprove f(n) = 5 · n3 n + 3
  2. f(n) = O(n2)

f(n) = O(n2) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · n2 n k

Which is a contradiction, hence f(n) 6= O(n2).

  1. f(n) = Ω(n)

f(n) = Ω(n) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≥ c · nn k

5 · n3 n + 3 ≥ 5 · n n + 3

≥ 5 · n n

= 4 · n,n ≥ 1

Let c = 4 and k = 1 then the statement translate to

5 · n3 n + 3 ≥ c · n,n k

which by the definition of Ω notation, 5 · n3 n + 3 is Ω(n).

  1. f(n) = Θ(n3)

f(n) = Θ(n3) ⇐⇒ f(n) = O(n3)andf(n) = Ω(n3)

Showing f(n) = O(n3)

f(n) = O(n3) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

5 · n3 n + 3 ≤ 5 · n3 + n3 + 3 · n3

= 9 · n3,n ≥ 1

Let c = 9 and k = 1 then the statement translates to

5 · n3 n + 3 ≤ c · n3,n k

which by the definition of O notation, 5 · n3 n + 3 = O(n3).

Showing f(n) = Ω(n3) f(n) = Ω(n3) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≥ c · g(n)∀n k

5 · n3 n + 3 ≥ 5 · n3 n3 + 3

≥ 4 · n3 + 3

≥ 4 · n3,n ≥ 1

Let c = 4 and k = 1 then the statement translate to

5 · n3 n + 3 ≥ c · n3,n k

which by the definition of Ω notation, 5 · n3 n + 3 is Ω(n3).

Since 5 · n3 n + 3 is O(n3) and 5 · n3 n + 3 is Ω(n3) we conclude that 5 · n3 n + 3 is Θ(n3).

  1. f(n) = ω(n)

which by the definition of ω notation, 5 · n3 n + 3 is ω(n).

  1. f(n) = o(n2)

hence f(n) 6= o(n2).

  1. Prove that (n + 5)100 = Θ(n100)

f(n) = Θ(g(n)) ⇐⇒ f(n) = O(g(n))andf(n) = Ω(g(n))

  1. Showing (n + 5)100 = O(n100)

f(n) = O(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

Let and k = 1 then the statements translates to

f(n) ≤ c · g(n),n k

which by the definition of O notation f(n) = O(g(n)).

  1. Showing (n + 5)100 = Ω(n100)

f(n) = Ω(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≥ c · g(n)∀n k

Let c = 1 and k = 1 then the statement translates to

f(n) ≥ c · g(n),n k

which by the definition of Ω notation f(n) = Ω(g(n)).

Since f(n) = O(g(n)) and f(n) = Ω(g(n)) by the definition of Θ notation f(n) = Θ(n100).

  1. Prove transitivity of big-O: if f(n) = O(g(n)), and g(n) = O(h(n)), then f(n) = O(h(n)).

Since f(n) = O(g(n)) and g(n) = O(h(n)) we have the equalities

f(n) ≤ c1 · g(n),n k1 g(n) ≤ c2 · h(n),n k2

From this we obtain

f(n) ≤ c1 · c2 · h(n),n k0

where k0 = max(k1,k2). Let c = c1 ·c2 and k = k0 the statement then translate to

f(n) ≤ c · h(n),n k

which by the definition of O notation, f(n) = O(h(n)).

  1. Prove that f(n) = O(g(n)) ⇐⇒ g(n) = Ω(f(n)).

Forward direction: f(n) = O(g(n)) =⇒ g(n) = Ω(f(n)).

Since f(n) = O(g(n)) there exists a number c and a number k such that f(n) ≤ c · g(n),n k where c > 0 and k ≥ 0. From this we obtain g(n),n k. Which by the definition of Ω notation, g(n) = Ω(f(n)).

Backward direction: g(n) = Ω(f(n)) =⇒ f(n) = O(g(n))

Since g(n) = Ω(f(n)) there exists a number c and a number k such that g(n) ≥ c · f(n),n k where c > 0 and k ≥ 0. From this we obtain f(n),n k. Which by the definition of O notation, f(n) = O(g(n)).

We conclude f(n) = O(g(n)) ⇐⇒ g(n) = Ω(f(n)).

  1. Compare the growth of
    1. f(n) = n and g(n) = n1+sin(n)

f(n) = O(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

No analysis can be described for f(n) and g(n).

  1. f(n) = n and g(n) = n + sin(n)

√ √

Thus n is o(n + sin(n)). This implies n is O(n + sin(n)). We also

have then that n + sin(n) is Ω( n).

  1. f(n) = n and g(n) = n |sin(n)|

f(n) = O(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

n · |sin(n)| ≤ c · n

|sin(n)| ≤ c

Let c = 2 and k = 0 then the following equality holds

n · |sin(n)| ≤ c · n k

by the definition of O notation n · |sin(n)| is O(n). by part (7) we also have that n is Ω(n · |sin(n)|).

  1. Prove or disprove 2n+1 = O(2n)

f(n) = O(g(n)) ⇐⇒ ∃c > 0,k ≥ 0s.tf(n) ≤ c · g(n)∀n k

2n+1 = 2 · 2n

≤ 3 · 2n,n ≥ 1

Let c = 3 and k = 1 then the statement translates to

2n+1 c · 2n,n k

which by the definition of O notation, 2n+1 = O(2n).

  1. Prove or disprove 2n = (2n)

hence 2n 6= o(2n).

  1. Prove that if f(n) ≤ Θ(g(n)).

, for some constant C > 0 then

Since, for every > 0, there exists k ≥ 0 such that, for all

. From this we obtain

Since C > 0 and > 0, the equality implies f(n) = Θ(g(n)) so long as ( 0. Let then the equality holds and by the definition of Θ notation, f(n) = Θ(g(n)).

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Shopping Cart
[Solved] CECS328 hw2
10 USD $