Mathematics Homework Solutions
Problem
#65093

Big O notation

i) Show that x^3 is O(x^4) but x^4 is not O(x^3)
ii)Show that xlnx is O(x^2) but x^2 is not O(xlnx)
iii)Show that  a^x O(b^x)  but b^x is not O(a^x)
if 0 < a <  b  (0 = zero)

iv)Show that 1^k + 2^k+...+n^k is O(n^(k+1)) for every positive integer k


Solution Summary

This provides several examples of working with Big O.

Solution
What is this?
By OTA - Overall OTA Rating
Yupei Xiong, PhD - 4.8/5
Purchase Cost Now
$2.19 CAD (was ~$11.97)
Included in Download
  • Plain text response
  • Attached file(s):
    • 65093.doc
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
  • Big-O Big-Theta - Given the algorithm below, suppose the number of times the "beep" instruction is executed is f(n). Choose all true statements below, and no false ones... for i := 1 to n for j : = 1 to i ...
  • Pick all correct answers - Question Pick all correct answers: If f(x) = 3x^2 + 4ln(x) + 9, then f(x) is:... a. Big-Theta of g(x) = x^2 b. Big-Omega of g(x) = 1 c. An unimpressive time-cost function for a s ...
  • Context Free Grammars - Following is a big-oh relationship. Give witnesses n0 and c that can be used to prove the relationship. Choose your witnesses to be minimal, in the sense that n0 - 1 and c are not witnesses, and if ...
  • Big-oh - A.Use the definition of big-oh to prove that (3n-8-4n^3)/(2n-1)is O(n^2) B.Use the definition of big-oh to prove that 1 • 2 + 2 • 3 + 3 • 4 + ... + (n - 1) • n is O(n^3).
  • Big-Oh Function - Please see the attached file for the fully formatted problems. I need to find the best big-oh function for the function. I need to choose my answer from among the following: 1, log2 n, n, n log2 n, ...
Browse