Determing when f(x) and g(x) are in theta of h(x)

  • Context: MHB 
  • Thread starter Thread starter Lepros
  • Start date Start date
  • Tags Tags
    Theta
Click For Summary
SUMMARY

If f(x) is in Θ of h(x) and g(x) is in Θ of h(x), then f(x) + g(x) is also in Θ of h(x). This conclusion is based on the properties of asymptotic notation, specifically that the addition of two functions in Θ does not alter their growth rate relative to h(x). To formally prove this, one must utilize the definitions of Θ notation for both f(x) and g(x) and apply appropriate proof techniques from discrete mathematics.

PREREQUISITES
  • Understanding of asymptotic notation, specifically Θ notation
  • Familiarity with discrete mathematics concepts
  • Basic knowledge of function growth rates
  • Experience with proof techniques in mathematics
NEXT STEPS
  • Study the formal definitions of Θ notation in algorithm analysis
  • Learn about proof techniques in discrete mathematics, such as direct proof and contradiction
  • Explore examples of function growth rates and their implications in algorithm efficiency
  • Investigate the relationship between polynomial and non-polynomial functions in asymptotic analysis
USEFUL FOR

This discussion is beneficial for computer scientists, mathematicians, and students studying algorithm analysis, particularly those interested in discrete mathematics and asymptotic notation.

Lepros
Messages
3
Reaction score
0
If f(x) is in theta of h(x) and g(x) is in theta of h(x), then is f(x)+g(x) in theta of h(x)?

My initial thoughts on this are yes since the addition of the two functions shouldn't impact the value of the largest degree in both functions, as they would if they were multiplied, but I'm wondering what sort of proof technique I could use to prove this in a more mathematically sound way.
 
Mathematics news on Phys.org
You are right about the answer. However, you can't talk about the largest degree because f(x) and g(x) are not necessarily polynomials. To prove the statement formally, start by writing what $f(x)\in\Theta(h(x))$ and $g(x)\in\Theta(h(x))$ means by definition.

I believe this answer is suitable for the Discrete Mathematics section of this forum because $\Theta$ is often used in measuring discrete resources consumed by algorithms.
 

Similar threads

  • · Replies 5 ·
Replies
5
Views
1K
  • · Replies 2 ·
Replies
2
Views
1K
Replies
1
Views
1K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 11 ·
Replies
11
Views
2K
Replies
5
Views
1K
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 13 ·
Replies
13
Views
2K
Replies
7
Views
2K