Solving Simple Homework Problems: An Exercise in O(x^4) Analysis

Click For Summary
SUMMARY

The discussion focuses on determining whether the function f(x) = x^4 + 9x^3 + 4x + 7 is O(x^4). The participant demonstrates their approach by establishing the inequality |x^4 + 9x^3 + 4x + 7| ≤ C|x^4| for x > k, concluding with C=21 and k=1. However, the textbook specifies C=4 and k=9, leading to a debate about the significance of constant values in Big O notation. Ultimately, the consensus is that while constants can vary, they do not affect the validity of the Big O classification.

PREREQUISITES
  • Understanding of Big O notation and asymptotic analysis
  • Familiarity with polynomial functions and their growth rates
  • Basic knowledge of inequalities and limits
  • Experience with mathematical proofs and problem-solving techniques
NEXT STEPS
  • Study the principles of Big O notation in detail
  • Learn how to analyze polynomial functions for asymptotic behavior
  • Explore the significance of constants in Big O notation
  • Practice solving various types of asymptotic analysis problems
USEFUL FOR

Students in computer science or mathematics, particularly those struggling with algorithm analysis and asymptotic notation, will benefit from this discussion.

TheLegace
Messages
26
Reaction score
0

Homework Statement


Hi, I have been having huge problems with dealing with these kinds of problems, I would appreciate atleast some guidance in dealing with these sorts of problems, I think the major problem is just how I learned to solve them, I have been looking for resources on the net, but it just gets to complicated, and I need someone to help me start with simple stuff first.

A very simple problem I am starting with will be this one:

Is x^4 + 9x^3 + 4x + 7 O(x^4) ?


Homework Equations


Well obviously start with:

|x^4 + 9x^3 + 4x + 7| ≤ C|x^4|

The Attempt at a Solution



Now if I try working this out

|x^4 + 9x^3 + 4x + 7| ≤ C|x^4| for all x > k
x^4 + 9x^3 + 4x + 7 ≤ 1x^4 + 9x^4 4x^4 7x^4 for all x > 1
f(x) ≤ 21x^4 for all x > 1
so for C=21 and k=1 f(x) = O(x^4).

Now the solution in the textbook says the constants are C=4, k=9.
Am I wrong or do the constants matter, I know there are infinite amount of constants if the statement is true, but why choose those ones anyway then?

Any help would be appreciated.
Thank You.
 
Physics news on Phys.org
I like your way. Simple and direct. The actual constants don't matter.
 

Similar threads

  • · Replies 16 ·
Replies
16
Views
3K
  • · Replies 6 ·
Replies
6
Views
2K
Replies
4
Views
2K
Replies
2
Views
1K
  • · Replies 4 ·
Replies
4
Views
1K
  • · Replies 18 ·
Replies
18
Views
6K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 25 ·
Replies
25
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 10 ·
Replies
10
Views
2K