[Solved] CECS328 hw2

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) = 2n²nlog₂(n)+3log₂(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) = 2n⁴log₂(n⁴)n²+3log₂(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 nn 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ⁿ)

hence 2²ⁿ 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)).