Finding the Big O of polynomials

In summary, the conversation discusses the use of the definition of "f(x) is O(g(x))" to prove that 2^x + 17 is O(3^x) and determining whether x^4/2 is O(x^2). The speaker mentions that they are unsure of how to prove this mathematically and expresses their struggle with understanding big O, requesting for some intuition.
  • #1
IAmPat
29
0

Homework Statement



1. Use the definition of "f(x) is O(g(x))" to show that 2^x + 17 is O(3^x)').
2. Determine whether the function x^4/2 is O(x^2)


2. The attempt at a solution

1. From my understanding, I would say of course 2^x + 17 is O(3^x) because the constant is of such low order that 2^x would never reach 3^x. I don't know how to prove it mathematically though.

2. To be honest, I just don't understand the steps I need to take to prove or disprove this. I have a vague understanding of big O but even with teacher examples and lots of googling, it seems like nobody knows what the hell they're talking about. I need some intuition
 
Physics news on Phys.org
  • #2
how about starting with the definition of big Oh
 

Related to Finding the Big O of polynomials

What is the Big O of a polynomial?

The Big O of a polynomial is a way to measure the growth rate of a function as the input size increases. It represents the upper bound on the number of operations required to solve the problem, and is used to analyze the time complexity of algorithms.

How do you find the Big O of a polynomial?

To find the Big O of a polynomial, you can look at the highest degree term in the polynomial. This will determine the overall growth rate of the function and its time complexity. For example, a polynomial with a term of n^2 would have a Big O of O(n^2).

Can the Big O of a polynomial change?

Yes, the Big O of a polynomial can change depending on the input size and the specific terms in the polynomial. It is important to analyze the worst-case scenario to determine the overall Big O.

What is the difference between Big O and Big Theta?

Big O represents the upper bound on the growth rate of a function, while Big Theta represents both the upper and lower bounds. This means that Big Theta provides a more accurate measure of the actual growth rate of a function.

Why is it important to find the Big O of polynomials?

Finding the Big O of polynomials is important because it allows us to analyze the time complexity of algorithms and determine their efficiency. By understanding the growth rate of a function, we can make informed decisions about which algorithms to use for different problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
9
Views
568
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
873
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
357
  • Calculus and Beyond Homework Help
Replies
8
Views
971
  • Calculus and Beyond Homework Help
Replies
3
Views
933
Back
Top