Test 12-16

From harvested file: duybt__function.doc

Without templates

Theorem 1: a n x n + ... + a 1 x + a 0   is   O ( x n )   for any real numbers a n , ..., a 0 and any nonnegative number n .

With templates

an xn + ... + a1 x + a0   is   O( xn )   for any real numbers an , ..., a0 and any nonnegative number n .

From harvested file: he__deceives_report-no-appendix.doc

Without templates

Theorem 1: calling makeLayer with valid inputs (a list of weights and two non-zero natural numbers) returns a valid layer recognized by isLayer. (“layers.lisp”)

Theorem 2: calling makeNetwork with valid inputs (a list of non-zero natural numbers and a list of weights) returns a valid network recognized by isNetwork. (“networks.lisp”)

With templates

calling makeLayer with valid inputs (a list of weights and two non-zero natural numbers) returns a valid layer recognized by isLayer. (“layers.lisp”)

calling makeNetwork with valid inputs (a list of non-zero natural numbers and a list of weights) returns a valid network recognized by isNetwork. (“networks.lisp”)

From harvested file: duybt__function.doc

Without templates

Theorem 4: a n x n + ... + a 1 x + a 0   is   θ ( x n )   for any real numbers a n , ..., a 0 and any nonnegative number n .

Let f ( x ) and g ( x ) be functions from a set of real numbers to a set of real numbers.

Then

1.     If   $f(x)/g(x)=0$ , then   f ( x ) is  o ( g ( x ) ) . Note that if   f ( x ) is  o ( g ( x ) ), then  f ( x ) is  O ( g ( x ) ).

2.     If  $f(x)/g(x)=\infty$ , then   g ( x ) is o ( f ( x ) ) .

3.     If   , then   f ( x ) is θ ( g ( x ) ) .

4.     If   , then   f ( x ) is O ( g ( x ) ) .

For example,

$$ (4x ³ + 3x ² + 5)/(x ⁴ – 3x ³ – 5x -4)  

= $$ ( 4/x + 3/x 2 + 5/x 4 )/( 1 - 3/x - 5/x 3 - 4/x 4 ) = 0 .

Hence

( 4x 3 + 3x 2 + 5 )   is   o ( x 4 - 3x 3 - 5x - 4 ),  

or equivalently,   ( x 4 - 3x 3 - 5x - 4 ) is   ω ( 4x 3 + 3x 2 + 5 ) .

Let us see why these rules hold. Here we give a proof for 4. Others can be proven similarly.

Proof : Suppose   .

By the definition of limit this means that

∀ε>0, ∃ n ₀ such that   | f(x)/g(x) – C 1 |<ε whenever x> n ₀

Hence –ε < f(x)/g(x) – C 1 <ε

Hence –ε + C 1 < f(x)/g(x) <ε + C 1

In particular f(x)/g(x) <ε + C 1

Hence f(x) <(ε + C 1 ) g(x)

Let C = ε + C 1 , then f(x) < Cg(x) whenever x> n _{0 .}

Since we are interested in non-negative functions f and g , this means that   | f ( x ) | ≤ C | g ( x ) |

Hence   f ( x ) = O ( g ( x ) ) .

With templates

an xn + ... + a1 x + a0   is   θ( xn )   for any real numbers an , ..., a0 and any nonnegative number n .

Let f(x) and g(x) be functions from a set of real numbers to a set of real numbers.

Then

1.     If   $f(x)/g(x)=0$ , then  f(x) is o( g(x) ) . Note that if  f(x) is o( g(x) ), then f(x) is O( g(x) ).

2.     If  $f(x)/g(x)=\infty$ , then   g(x) is o( f(x) ) .

3.     If   , then   f(x) is θ( g(x) ) .

4.     If   , then   f(x) is O( g(x) ) .

For example,

$$ (4x3 + 3x2 + 5)/(x4 – 3x3 – 5x -4) 

= $$ ( 4/x + 3/x2 + 5/x4 )/(1 - 3/x - 5/x3 - 4/x4 ) = 0 .

Hence

( 4x3 + 3x2 + 5 )   is   o(x4 - 3x3 - 5x - 4 ),  

or equivalently,   (x4 - 3x3 - 5x - 4 ) is   ω(4x3 + 3x2 + 5 ) .

Let us see why these rules hold. Here we give a proof for 4. Others can be proven similarly.

Proof: Suppose   .

By the definition of limit this means that

∀ε>0, ∃n0 such that   |f(x)/g(x) – C1|<ε whenever x>n0

Hence –ε<f(x)/g(x) – C1<ε

Hence –ε +C1<f(x)/g(x)<ε +C1

In particular f(x)/g(x)<ε +C1

Hence f(x)<(ε +C1)g(x)

Let C = ε +C1 , then f(x)<Cg(x) whenever x>n0 .

Since we are interested in non-negative functions f and g, this means that   |f(x) | ≤C | g(x) |

Hence   f(x) = O( g(x) ) .

test