Let f(n) 10n +81n + n+ log2 n. Prove that f(n) = O(n). = 3. (10...

  

Transcribed Image Text:

Let f(n) 10n +81n + n+ log2 n. Prove that f(n) = O(n). = 3. (10 pts) Prove that O(n) + O(n) 0(n). 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(n) + f2(n), where fi(n) = O(n) and f(n) = O(n). E 4. (10 pts) Prove that O(n) + O(n) #0 (n). Let f(n) 10n +81n + n+ log2 n. Prove that f(n) = O(n). = 3. (10 pts) Prove that O(n) + O(n) 0(n). 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(n) + f2(n), where fi(n) = O(n) and f(n) = O(n). E 4. (10 pts) Prove that O(n) + O(n) #0 (n).

Answer rating: 100% (QA)

It appears that you are working with proving statements about the Big O Theta and little o notations which are used in computer science to describe th... View the full answer