Show that x^3 is O(x^4) but that x^4 is not

William Boggs 2021-12-19 Answered
Show that x3 is O(x4) but that x4 is not O(x3).
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Expert Answer

Jack Maxson
Answered 2021-12-20 Author has 25 answers
Defintions
Big-O Notation: f(x) is O(g(x)) is there exists constants C and k such that
|f(x)|C|g(x)|
Whener x>k
Note: Choises of C and k are not unique.
Solution:
First part
f(x)=x3
g(x)=x4
For convevience sake, we will choose k=1 and thus x>1.
|f(x)|=|x3|
=x3
1x3
<xx3
=x4
=|x4|
Thus we need to choose C to be at least 1. Let us then take C=1
By the definition of Big-O notation, f(x)=x3 is O(x4) with k=1 and C=1.
Second part
f(x)=x4
g(x)=x3
Let us assume that f(x)=x4 is O(x3). Then there exist constants C and k such that:
|x4|C|x3|
when x>k
Let us assume C0, which is a safe assumption.
|x4|C|x3|=|Cx3|
We have then obtained a contradiction, because |x4|>|Cx3| when x>C
Thus f(x)=x4 is not O(x3)
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-02-10
A 230kg crate hangs from the end of a rope of length L=12.0m. You push horizontally on the crate with a varying force F to move it distance d= 4.00m to the side.
a) What is the magnitude of F when the crate is in this final position? What are b) the total work done on it, c) the work done by the gravitational force on the crate, and d) the work done by the pull on the crate fromthe rope? e) Knowing the the crate is motionless before and after its displacement, use the answers to (b), (c), and (d) to find the work your force F does on the crate. f) Why is the work of your force not equal to the product of the horizontal displacement and the answer to (a)?
asked 2020-11-01
As part of your work out, you lie on your back and push with your feet against a platform attached to two stiff springs arranged side by side so that they are parallel to each other. when u push the platform, you compress the springs. You do 80.0G of work when u compress the springs 0.200m from their uncompressed length.
a) What magnitude of force must u apply to hold the platform in this position?
b) How much additional work must you do to move the platform 0.200m farther, and what maximum force must you apply?
asked 2021-03-13
When a person stands on tiptoe (a strenuous position), the position of the foot is as shown in Figure (a). The total gravitational force on the body, vector F g, is supported by the force vector n exerted by the floor on the toes of one foot. A mechanical model of the situation is shown in Figure (b), where vector T is the force exerted by the Achilles tendon on the foot and vector R is the force exerted by the tibia on the foot. Find the values of vector T , vector R , and θ when vector F g = 805 N. (Do not assume that vector R is parallel to vector T .)
asked 2021-01-31
For tests using a ballistocardiograph, a patient lies on a horizontal platform that is supported on jets of air. Because of the air jets, the friction impeding the horizontal motion of the platform is negligible. Each time the heart beats, blood is pushed out of the heart in a direction that is nearly parallel to the platform. Since momentum must be conserved, the body and the platform recoil, and this recoil can be detected to provide information about the heart. For each beat, suppose that 0.050 kg of blood is pushed out of the heart with a velocity of +0.30 m/s and that the mass of the patient and the platform is 85 kg. Assuming that the patient does not slip with respect to the platform, and that the patient and the platform start from rest, determine the recoil velocity.
asked 2020-12-03
Calculate the minimum concentration of Cr3+ thatmust be added to 0.095M NaF in order to initiate a precipitate ofchromium(III) fluoride. (For CrF3, Ksp= 6.6×1011)
asked 2021-10-19

The article “Evaluating Vent Manifold Inerting Requirements: Flash Point Modeling for Organic Acid-Water Mixtures” presents a model to predict the flash point (in \(\displaystyle{F}^{{\circ}}\)) of a mixture of water, acetic acid, propionic acid, and butyric acid from the concentrations (in weight %) of the three acids. The results are as follows. The variable “Butyric Acid \(\displaystyle\times\) Acetic Acid” is the interaction between butyric acid concentration and acetic acid concentration.
\(\begin{array}{|c|c|}\hline text{Predictor} & \text{Coef} & \text{SE Coef} & T & P \\ \hline \text{Constant} & 267.53 & 11.306 & 23.66 & 0.000 \\ \hline \text{Acetic Acid} & -1.5926 & 0.1295 & -12.30 & 0.000 \\ \hline \text{Propionic Acid} & -1.3897 & 0.1260 & -11.03 & 0.000 \\ \hline \text{Butyric Acid} & -1.0934 & 0.1164 & -9.39 & 0.000 \\ \hline \text{Butyric Acid} \times\text{Acetic Acid} & -0.002658 & 0.001145 & -2.32 & 0.034 \\ \hline \end{array}\)
a) Predict the flash point for a mixture that is 30% acetic acid, 35% propionic acid, and 30% butyric acid. (Note: In the model, 30% is represented by 30, not by 0.30.)
b) Someone asks by how much the predicted flash point will change if the concentration of acetic acid is increased by 10% while the other concentrations are kept constant. Is it possible to answer this question? If so, answer it. If not, explain why not.
c) Someone asks by how much the predicted flash point will change if the concentration of propionic acid is increased by 10% while the other concentrations are kept constant. Is it possible to answer this question? If so, answer it. If not, explain why not.

asked 2021-11-27

Refer to the accompanying data display that results from a sample of airport data speeds in Mbps. Complete parts (a) through (c) below.
Tinterval (13.046, 22.15)
x=17.598
Sx=16.01712719
n=50
Express the confidence interval in the format that uses the "less than" symbol. Given that the original listed data use one decimal place, round the confidence interval limits accordingly.
?Mbps<μ<?Mbps

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question