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

  • Thread starter needhelp83
  • Start date
  • Tags
    Notation
In summary, the conversation discusses the Big-O Notation and its use in comparing the growth of number-theoretic functions. The questions ask whether adding or multiplying a function will change its level in the sequence. In both cases, the answer is no, as the level is determined by the highest exponent in the function.
  • #1
needhelp83
199
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
  • #2
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:
  • #3


Asymptotic notation is a mathematical tool used to describe the behavior of functions as the input size, denoted by N, approaches infinity. In this context, the statement "f(N) + g(N) = O(h(N))" means that the sum of the functions f(N) and g(N) will not grow faster than h(N) as N gets larger. Similarly, the statement "f(N) * g(N) = O(h(N))" means that the product of f(N) and g(N) will not grow faster than h(N) as N gets larger.

In order to determine if these statements are true, we need to understand the definition of big O notation. In general, a function f(N) is said to be O(g(N)) if there exists a constant C and a value N0 such that for all values of N greater than or equal to N0, f(N) is less than or equal to Cg(N). In other words, f(N) is bounded by a constant multiple of g(N) for sufficiently large values of N.

Now, let's apply this definition to the statements in question.

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

To answer this, we need to show that there exists a constant C and a value N0 such that for all values of N greater than or equal to N0, f(N) + g(N) is less than or equal to Ch(N). This is true because if f(N) = O(h(N)) and g(N) = O(h(N)), then there exists constants C1 and C2 and values N1 and N2 such that for all values of N greater than or equal to N1, f(N) is less than or equal to C1h(N) and for all values of N greater than or equal to N2, g(N) is less than or equal to C2h(N). Therefore, for all values of N greater than or equal to max(N1, N2), we have f(N) + g(N) is less than or equal to C1h(N) + C2h(N) = (C1 + C2)h(N), where C = C1 + C2 and N0 = max(N1, N2). This satisfies the definition of big O notation, hence f(N) + g(N) = O(h(N)) is true.

2. Is f(N
 

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

1. What is asymptotic notation?

Asymptotic notation is a mathematical tool used to analyze and describe the behavior of functions as their input size approaches infinity. It is commonly used in computer science to analyze the time and space complexity of algorithms.

2. What does f(N)+g(N)=O(h(N)) mean?

This notation is read as "f of N plus g of N is big O of h of N." It means that the sum of the functions f(N) and g(N) grows at a rate no faster than the function h(N) as N approaches infinity. It is used to describe the upper bound or worst-case scenario of a function's growth.

3. How is asymptotic notation useful?

Asymptotic notation allows us to compare the efficiency of algorithms and determine which one will be more efficient for large inputs. It also helps in analyzing the scalability of a program and making decisions on how to optimize it.

4. What is the difference between f(N)+g(N)=O(h(N)) and f(N)*g(N)=O(h(N))?

The first notation describes the upper bound of the sum of two functions, while the second notation describes the upper bound of the product of two functions. This means that the first notation describes the worst-case scenario of the sum of two functions, while the second notation describes the worst-case scenario of the product of two functions.

5. Can asymptotic notation be used for all types of functions?

No, asymptotic notation is typically used for functions that represent the time or space complexity of algorithms. It is not suitable for all types of functions, such as periodic or oscillating functions.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
968
  • Engineering and Comp Sci Homework Help
Replies
6
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Quantum Physics
Replies
3
Views
137
Back
Top