Please explain how you attacked these questions step by step. 1) 1 is not O(1/x). 2) e^x is not O(x^5)

Luz Stokes 2022-07-18 Answered
I'm studying for my discrete math class and I don't fully understand how to proof how a function is not a big O for certain questions. I understand that you have to assume that it is big O and proof by contradiction.
Please explain how you attacked these questions step by step.
1) 1 is not O ( 1 x )
2) e x is not O ( x 5 )
You can still ask an expert for help

Want to know more about Discrete math?

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

Answers (1)

frisiao
Answered 2022-07-19 Author has 13 answers
Step 1
1) Suppose 1 = O ( 1 / x ). Then there exists a constant C such that for all large x, we have 1 C / x. However, for all x > C we have C / x < 1, a contradiction.
Step 2
2) Suppose e x = O ( x 5 ). Then there exists a constant C such that for all large x we have e x C x 5 . However, e x x 5 as x , a contradiction. [As Peter suggests, use L'Hopital's rule multiple times, or expand the Taylor series for e x .]
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-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2021-08-02
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
a) the set of sophomores taking discrete mathematics in your school
b) the set of sophomores at your school who are not taking discrete mathematics
c) the set of students at your school who either are sophomores or are taking discrete mathematics
Use these symbols:
asked 2022-07-14
In how many ways can you sit 5 people in a row of 20 seats if no 2 can sit together?
I've seen the simpler problem of just sitting 2 people in non consecutive seats. In that case, I would subtract from the total number of ways to sit the 2 persons the number of ways of sitting them together.
In this harder version of the problem,I've though of the same thing, but now considering the case were 2, 3, 4 or 5 sit together. But that seems to count duplicate cases.
asked 2022-05-27
Let A = { 1 , 2 , . . . , n }, and R be a relation on A (so R A × A)
i) What is the minimal possible number of elements in R?
I tried calculating this as just a normal cartesian product which would have n 2 within the set. So R would also need n2 number of elements to be a proper subset of A × A.
ii) What is the maximal possible number of elements in R?
I'm a bit more confused by this one, but I think it would have something to do with calculating it as 2 n 2 i.e., if n was 3 then it would be 2 9 or 512 as the maximum number of elements.
asked 2022-05-22
You have {a,b,c} as your character set. You need to create words having 10 characters that must be chosen from the character set. Out of all the possible arrangements, how many words have exactly 6 as?

New questions

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