CECS328 hw2 Solved

Description

1. Prove that f(n) = 10 · n⁴ + 2 · n² + 3 is O(n⁴), provide the appropriate C and k

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

10 · n⁴ + 2 · n² + 3       ≤       10 · n⁴ + 2 · n⁴ + 3

≤        10 · n⁴ + 2 · n⁴ + 3 · n⁴

=       15 · n⁴,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))

2. Prove that f(n) = 2·n²−nlog₂(n)+3·log₂(n) is O(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 · n² − n · log₂(n) + 3 · log₂(n)        ≤        2 · n² + n² + 3 · log₂(n)

≤        2 · n² + n² + 3 · n²

=       6 · n²,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)).

3. Prove that f(n) = 2·n⁴log₂(n⁴)−n²+3·log₂(n) is O(n⁴log₂(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 · n⁴ · log₂(n⁴) − n² + 3 · log₂(n)           =        8 · n⁴ · log₂(n) − n² + 3 · log₂(n)

≤         8 · n⁴ · log₂(n) + n⁴ · log₂(n) + 3 · log₂(n)

≤         8 · n⁴ · log₂(n) + n⁴ · log₂(n) + 3 · n · log₂(n)

=        12 · n⁴ · log₂(n),n ≥ 1

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

2 · n⁴ · log₂(n⁴) − n² + 3 · log₂(n)         ≤        c · n⁴ · log₂(n),n ≥ 1

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

4. Prove or disprove f(n) = 5 · n³ − n + 3
5. f(n) = O(n²)

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

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

2. f(n) = Ω(n)

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

5 · n³ − 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 · n³ − n + 3       ≥       c · n,n ≥ k

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

3. f(n) = Θ(n³)

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

Showing f(n) = O(n³)

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

5 · n³ − n + 3        ≤        5 · n³ + n³ + 3 · n³

=        9 · n³,n ≥ 1

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

5 · n³ − n + 3       ≤        c · n³,n ≥ k

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

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

5 · n³ − n + 3       ≥        5 · n³ − n³ + 3

≥       4 · n³ + 3

≥       4 · n³,n ≥ 1

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

5 · n³ − n + 3       ≥        c · n³,n ≥ k

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

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

4. f(n) = ω(n)

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

5. f(n) = o(n²)

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

5. Prove that (n + 5)¹⁰⁰ = Θ(n¹⁰⁰)

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

1. Showing (n + 5)¹⁰⁰ = O(n¹⁰⁰)

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

2. Showing (n + 5)¹⁰⁰ = Ω(n¹⁰⁰)

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) = Θ(n¹⁰⁰).

6. 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)            ≤               c₁ · g(n),n ≥ k₁ g(n)               ≤               c₂ · h(n),n ≥ k₂

From this we obtain

f(n)       ≤        c₁ · c₂ · h(n),n ≥ ^k0

where k⁰ = max(k₁,k₂). Let c = c₁ ·c₂ and k = k⁰ the statement then translate to

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

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

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

8. Compare the growth of
   1. f(n) = n and g(n) = n^1+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).

√

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

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

9. Prove or disprove 2ⁿ⁺¹ = O(2ⁿ)

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

2n+1       =      2 · 2n

≤        3 · 2ⁿ,n ≥ 1

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

2ⁿ⁺¹       ≤        c · 2ⁿ,n ≥ k

which by the definition of O notation, 2ⁿ⁺¹ = O(2ⁿ).

10. Prove or disprove 2^2·n = (2ⁿ)

hence 2^2·n 6= o(2ⁿ).

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