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
Click For Summary
SUMMARY

In the discussion regarding asymptotic notation, it is established that if f(N) = O(h(N)) and g(N) = O(h(N)), then f(N) + g(N) = O(h(N)) holds true. This is due to the properties of Big-O notation, which allows for the addition of functions that grow at the same rate. However, f(N) * g(N) = O(h(N)) does not necessarily hold, as the product of two functions can grow faster than the individual functions. The discussion emphasizes the importance of understanding the growth rates of functions in algorithm analysis.

PREREQUISITES
  • Understanding of Big-O Notation
  • Familiarity with growth rates of functions
  • Basic knowledge of algorithm analysis
  • Concept of number-theoretic functions
NEXT STEPS
  • Study the properties of Big-O Notation in depth
  • Learn about the implications of function addition and multiplication in algorithm analysis
  • Explore examples of number-theoretic functions and their growth rates
  • Investigate other asymptotic notations such as Big-Theta and Big-Omega
USEFUL FOR

Students, computer scientists, and software engineers who are studying algorithm complexity and performance optimization will benefit from this discussion.

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:

[tex]f_2 = log_2 n[/tex]
.
.
.
[tex]f_{7.2} = n^2[/tex]
[tex]f_{7.3} = n^3[/tex]
.
.
.
[tex]f_{7.k} = n^k[/tex]
.
.

Now answer these questions:

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

Similar threads

  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K