Finding the Big O of polynomials

  • Thread starter Thread starter IAmPat
  • Start date Start date
  • Tags Tags
    Polynomials
Click For Summary
SUMMARY

The discussion focuses on determining the Big O notation for the functions 2^x + 17 and x^4/2. It is established that 2^x + 17 is O(3^x) because the exponential growth of 3^x outpaces that of 2^x, making the constant term negligible. The second function, x^4/2, is not O(x^2) as x^4 grows faster than x^2, thus failing the Big O condition. The participants express a need for a clearer understanding of the mathematical proofs involved in these determinations.

PREREQUISITES
  • Understanding of Big O notation and its formal definition
  • Basic knowledge of exponential functions and their growth rates
  • Familiarity with polynomial functions and their properties
  • Ability to analyze mathematical proofs and inequalities
NEXT STEPS
  • Study the formal definition of Big O notation and its mathematical implications
  • Learn about the growth rates of exponential functions compared to polynomial functions
  • Explore examples of proving Big O relationships using limits
  • Practice with additional problems involving Big O notation to solidify understanding
USEFUL FOR

Students in computer science or mathematics, particularly those studying algorithms and complexity analysis, as well as anyone seeking to understand the implications of Big O notation in function growth comparisons.

IAmPat
Messages
28
Reaction score
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
how about starting with the definition of big Oh
 

Similar threads

Replies
2
Views
2K
Replies
6
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 18 ·
Replies
18
Views
6K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
9
Views
3K
Replies
5
Views
2K
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K