- Accounting Homework Help
- Biology Homework Help
- Chemistry Homework Help
- Computer Science Help
- Economics Homework Help
- Engineering Homework Help
- English Homework Help
- Essay Writing Services
- Finance Homework Help
- Management Homework Help
- Math Homework Help
- Matlab Programming Help
- Online Exam Help
- Online Quiz Help
- Physics Homework Help
- Statistics Homework Help

- Physics Assignment Help
- Chemistry Assignment Help
- Math Assignment Help
- Biology Assignment Help
- English Assignment Help
- Economics Assignment Help
- Finance Assignment Help
- Statistics Assignment Help
- Accounting Assignment Help
- Computers Assignment Help
- Engineering Assignment Help
- Management Assignment Help

Explain big oh theory. What kind of properties does it have?

The following example gives the idea of one function growing more rapidly than another. We will use this example to introduce the concept the big-Oh.

Example: f(n) = 100 n2, g(n) = n4, the following table and Figure 2 show that g(n) grows faster than f(n) when n > 10. We say f is big-Oh of g.

Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be O( g(x) ) , which is read as f(x) is big-oh of g(x) , if and only if there are constants C and n0 such that

| f(x) | ≤ C | g(x) |

whenever x > n0 .

Note that big-oh is a binary relation on a set of functions (What kinds of properties does it have ? reflexive ? symmetric ? transitive ?).

The relationship between f and g can be illustrated as follows when f is big-oh of g.

For example, 5x + 10 is big-oh of x^{2}, because 5x + 10 < 5x^{2} + 10x^{2} = 15x^{2} for x > 1 .

Hence for C = 15 and n0 = 1 , | 5x + 10 | ≤ C | x^{2} | . Similarly it can be seen that 3x^{2} + 2 x + 4 < 9x^{2} for x > 1 . Hence 3x^{2} + 2 x + 4 is O( x^{2} ) . In general, we have the following theorem:

Theorem 1: a_{n} x_{n} + ... + a_{1} x + a_{0} is O( x_{n} ) for any real numbers an , ..., a0 and any nonnegative number n .

Note: Let f(x) = 3x^{2} + 2x + 4, g(x) = x^{2}, from the above illustration, we have that f(x) is

O(g(x)). Also, since x^{2} < 3x^{2} + 2 x + 4, we can also get g(x) is O(f(x)). In this case, we say these two functions are of the same order.