Question

1. a) Let f(n) = 6n² - 100n + 44 and g(n) = 0.5n³ . Prove that f(n) = O(g(n)) using the definition of Big-O notation. (You need to find constants c and n0).

b) Let f(n) = 3n² + n and g(n) = 2n² . Use the definition of big-O notation to prove that

1. f(n) = O(g(n)) (you need to find constants c and n0) and

2. g(n) = O(f(n)) (you need to find constants c and n0).

Conclude that f(n) = Θ(g(n)).

2. Order the following 16 functions by asymptotic growth rate from lowest to highest. If any are of the same order then circle them on your list.

5n-6, 3, 5n+n³, $\sqrt{n}$ , n^2.01, 3^log₂n, 4log n, n!, log n³, n^1/3, 3n³-5n+n⁴, n log n +4n, 10n⁴, 4ⁿ, 2ⁿ, 4ⁿ⁺¹. Note: When comparing two functions f(n) and g(n) you may use to compare their asymptotic growth rates.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

a)

Given f(n)=6n² - 100n + 44

g(n)=0.5*n^3

So, since we know that n^2<n^3 for all n>=1

So,

f(n)=6n² - 100n + 44<=6*n^3 for n>=1 because (44-100n)<0 for n>=1

So,

f(n)<=12*(0.5*n^3)

So, since we found c=12 and n0=1

f(n)=O(g(n))

b)

f(n)=3*n^2+n

g(n)=2*n^2

So,

f(n)=3*n^2+n<=3*n^2+n^2

So,

f(n)<=4*n^2

So,

f(n)<=2*(2n^2) for n>=1

So, since we found c=2 and n0=1

f(n)=O(g(n))

Note: Brother According to Chegg's policy we are only allowed to answer first Q if there are many. So, I request you to post other part as separate posts

Kindly revert for any queries

Thanks.