Asymptotic Notation: f(N)+g(N)=O(h(N))? f(N)*g(N)=O(h(N))?

  • Thread starter Thread starter needhelp83
  • Start date Start date
  • Tags Tags
    Notation
AI Thread Summary
If f(N) = O(h(N)) and g(N) = O(h(N)), then f(N) + g(N) = O(h(N)) holds true because the sum of two functions that are both upper-bounded by h(N) will also be upper-bounded by h(N). However, f(N) * g(N) = O(h(N)) does not necessarily hold, as the product of two functions can grow faster than h(N), depending on their specific growth rates. For example, if both f(N) and g(N) are polynomial functions, their product could exceed any linear bound. The discussion emphasizes understanding the implications of Big-O notation in function growth comparisons. Clarifying these concepts is crucial for analyzing algorithm efficiency.
needhelp83
Messages
193
Reaction score
0
Suppose f(N) = O(h(N)) and g(N) = O(h(N))

1. Is f(N) + g(N) = O(h(N))
2. Is f(N) * g(N) = O(h(N))

Justify answers

I am totally lost on these questions. ANY help would be greatly appreciated.
 
Physics news on Phys.org
This is the Big-O Notation. It is involved in comparing the growth of one number-theoretic function with that of another. There is a sequence of these functions. For instance:

f_2 = log_2 n
.
.
.
f_{7.2} = n^2
f_{7.3} = n^3
.
.
.
f_{7.k} = n^k
.
.

Now answer these questions:

Does adding n^2 to n^2 change the level in the sequence?
How about multiplying? (different constants don't count)
 
Last edited:

Similar threads

Replies
4
Views
2K
Replies
1
Views
2K
Replies
3
Views
1K
Replies
6
Views
2K
Replies
11
Views
2K
Replies
1
Views
2K
Replies
3
Views
2K
Replies
1
Views
631
Back
Top