Let fn 10n2 81n squareroot n log2 n Prove that fn elemen

Let f(n) = 10n^2 + 81n + squareroot n + log_2 n. Prove that f(n) element theta (n^2). Prove that theta (n) + O(n^2) subsetoforequalto O(n^2). Note that for this problem, you are proving that the set of functions on the left hand side (LHS) is a subset of the set of functions on the right hand side (RHS). The set on the LHS is the algebraic sum of two sets (not the union): an element of the LHS has the form f(n) = f_1(n) + f_2(n), where f_1(n) element theta (n) and f_2(n) element O (n^2). Prove that theta(n) + O(n^2) notequalto O(n^2).

Solution

1.f(n)=10n^2+81n+n+log n

=O(n^2)+O(n)+O(n)+O(log n)

=O(n^2)(since the highest power of the all function)

2.f1(n)+f2(n)=f(n)

assume,

n^2€O(n^2)

n€theta(n)

Hence, n+n^2=f(n)

f(n)is subset of O(n^2)

n+n^2is subset of O(n^2)

n+n^2is the subset of c(n^2)

n+1<cn

c>2

4 from the above proof we can prove the 4 the question