big "Oh" notation : Number Theory #BIG #oh #NOTATION #: #Number #Theory
big "Oh" notation :
Definition :
Suppose g(x) > 0 for all real values x ≥ a and f(x) is a real valued function
such that f(x)/g(x) is bounded for x ≥ a . Then we say that " f(x) is of large order g(x) " or "
f(x) is of order g(x) ".
In this case , we write f(x) = O(g(x)) ( we read f(x) is big Oh of g(x).
Equivalently , we can say that f(x) = O(g(x)) if there exists M > 0 such that | f(x)/g(x) | ≤ M
for all x ≥ a ,
or |f(x) | ≤ M |g(x)| or for all x ≥ a .
Note :
i) f(x) = h(x) + O g(x) means that f(x) - h(x) = O g(x) ⇒ | f(x) - h(x) | ≤ M g(x) for some M > 0.
ii) Suppose f(t) = O g(t) for t ≥ a ⇒ | f(t) | ≤ M g(t) for t ≥ a and for some M > 0.
⇒ ∫ | f(t) | dt ≤ ∫ M g(t) dt
⇒ ∫ | f(t) | dt ≤ M ∫ g(t) dt
⇒ ∫ | f(t) | dt ≤ O ( ∫ g(t) dt ) for x ≥ a.
Therefore f(t) = O (g(t) ) for t ≥ a implies that ∫ | f(t) | dt ≤ O ( ∫ g(t) dt ) for x ≥ a.
Examples :
1. Let f(x) = 20 x and g(x) = x.
Then f(x)/g(x) = 20 which is bounded.
Therefore f(x) = O(g(x)) or 20x = O (x) .
2. Suppose f(x) = 10 x2 and g(x) = 20 x4.
Then f(x)/g(x) = 10 x2
/ 20 x4 = 1 / 2 x2 < 1
Therefore f(x) = O
(g(x) ) or 10 x2 = O ( 20 x4 )
3. Suppose f(x) = 30x and g(x) = x and h(x) = 10x.
Then f(x) - h(x) = 30x-10x = 20x = O (x) = O (g(x) ).
⇒ f(x) = g(x) + O (g(x) )
Theorem 1 .
If g(x) >0 and lim ( f(x)/g(x) ) = L where L is finite , then f(x) = O (g(x) ).
Proof :
Suppose g(x) > 0 and lim ( f(x)/g(x) ) = L where L is finite.
Since lim ( f(x)/g(x) ) = L , given ϵ > 0 there exst N such that | f(x)/g(x) - L | < ϵ for all x ≥ N
⇒ | f(x)/g(x) | < ϵ + | L | for all x ≥ N.
Let ϵ + | L | = M.
Then | f(x)/g(x) | < M for all x ≥ N.
⇒ f(x)/g(x) is bounded for all x ≥ N.
⇒ f(x) = O (g(x) )
*** Hence the proof ***
Theorem 2 :
If f(x) > 0 and g(x) ≈ f(x), then f(x) = O(g(x) and g(x) = O (f(x) ).
Proof :
Let f(x) > 0 and f(x) ≈ g(x) .
Now lim (f(x)/g(x)) = 1 and lim (g(x)/f(x)) = 1.
Therefore for a given ϵ > 0 there exst N such that | f(x)/g(x) | < ϵ + 1 for all x ≥ N
and | g(x)/f(x) | < ϵ + 1 for all x ≥ N.
⇒ f(x) = O(g(x)) and g(x) = O(f(x))
*** Hence the Proof ***
Theorem 3 :
i) O(g(x)) +O(g(x)) =O(g(x))
ii ) If f(x) = O(g(x)) then O(f(x)) +O(g(x)) =O(g(x)).
Proof :
(i) Let f1 and f2 are two real valued functions and g(x) > 0 is a real valued function such
that f1(x) = O(g(x)) and f2(x) = O(g(x))
There fore there exist
number M1 and M2 such that | f1(x)/g(x)
| < M1 and | f2(x)/g(x) | < M2
Let M = M1 + M2.
Consider | (f1(x)+f2(x))/g(x)
| ≤ | f1(x)/g(x) | + | f2(x)/g(x)
| ≤ M1 + M2 = M
⇒ | (f1(x)+f2(x))/g(x)
| is bounded
⇒ f1(x)+f2(x) = O(g(x))
⇒ O(g(x)) +O(g(x)) =O(g(x)) | since f1(x) = O(g(x))
and f2(x) = O(g(x)) |
ii) Let f1 and f2 are two real valued functions and g(x) > 0 is a real valued function such that f1(x) = O(f(x)) and f2(x) = O(g(x)).
| f1(x)/g(x) | < M1 where M1
is a positive number ⇒ | f1(x) | ≤ M1 f(x)
……….(i)
and also
| f1(x)/g(x) | < M1 where M1
is a positive number ⇒ | f1(x) | ≤ M1 f(x)
……...(ii)
Given that f(x) = O(g(x)).
we have that
| f(x)/g(x) | ≤ M where M is a positive
number,
⇒ | f(x) | ≤ M |
g(x) | ………….(iii)
Consider | f1(x)+f2(x) | ≤ | f1(x) | +
| f2(x) |
≤ M1 | f(x) | + M2| g(x)
| | since from (i) and (ii) |
≤ M1
| g(x) |M + M2| g(x) | |
since from (iii |
≤ |g(x)| ( M1M + M2)
⇒ | (f1(x)+f2(x))/g(x) | ≤ M* where M* = M1M + M2
⇒ | (f1(x)+f2(x))/g(x) | is bounded
⇒ (f1(x)+f2(x) ≤ O(g(x))0
⇒ O(g(x)) +O(g(x)) =O(g(x))
*** Hence the Proof ***
BIG oh NOTATION : Number Theory
Comments
Post a Comment