ACE Take-Away: Tutorial No.1 Big-Oh Series

Take-Away Notes for Module COMP2048.

Completed
Corrected
Reviewed

Several functions that often appear in algorithm analysis:

General	Mathematical
Constant
Logarithmic	()
Linear
N-Log-N	()
Quadratic
Cubic
Exponential

Multiplication Rule for Big-Oh

1. Let , , , be functions mapping positive integers to positive real numbers. Show that if and , then .

Premise: 1. ; 2. , 3. , , , being functions mapping positive integers to positive real numbers;

Prof:

Given Premise 1:

Hence, by the definition of Big-Oh;

Given Premise 2:

Hence, by the definition of Big-Oh;

Given Premise 3: , , , be functions mapping positive integers to positive real numbers

Hence,

Set certain such that , ;

Hence, there exists positive real constant and positive integer such that ;

Hence, by the definition of Big-Oh.

Q.E.D.

Big-Oh Rules: Drop Smaller Terms

2. Let , be functions mapping positive integers to positive real numbers. Show that if with as , then .

Premise: 1. 2. as 3. , be functions mapping positive integers to positive real numbers

Proof:

Given Premise 2: as

Hence, there exists such that ;

Hence, ;

Hence, where , e.g. ;

Hence, ;

Q.E.D

Exercises 1-2

Apply the Big-Oh rules to justify the answers:

Exercise 3

Prove that:

Let ;

For , , where ;

Hence, , e.g. , .

Hence, .

Q.E.D.

Prove that:

Let ;

Let ;

For , , where ;

Hence, , e.g. , .

Hence, .

Q.E.D.

Exercise 4

Order the following function groups by asymptotic growth rate.

Note: ! The basis of log is 2 as default, equivalent to lb.

Exercise 5

1. Prove / Disprove:

Premise:

;

Statement:

, i.e. ;

Proof:

To prove the given statement is to prove:

;

Take arbitrary positive real constant , if the given statement is true:

, i.e,

by the definition of Little-Oh;

Take to be the smallest integer such that and ,

Hence, obviously, $n n_0 , , i.e, (f(n) cg(n))$;

Hence, , i.e. ,

Q.E.D.

2. Prove / Disprove:

Premise:

;

Statement:

, i.e. ;

Proof:

To prove the given statement is to prove:

;

Take arbitrary positive real constant , if the given statement is true:

, i.e,

by the definition of Little-Oh;

Take to be the smallest integer such that and ,

Hence, obviously, $n n_0 , , i.e, (f(n) cg(n))$;

Hence, , i.e. ,

Q.E.D.

3. Prove / Disprove:

Premise:

;

Statement:

, i.e. ;

Disproof: To prove by contradiction:

Suppose the given statement is true,

thus , i.e. ;

Hence, take arbitrary positive real constant ,

Given ,

obviously , i.e. ;

Hence, ;

Hence contradicts with the case ,

given all positive real constant such that .

Hence, the statement , i.e. is NOT true;

Q.E.D.

Counter Example:

When , there exists no cases such that , i.e. .

Exercise 6

1. Prove / Disprove:

Let ;

For c = 4, , where ;

Hence, , e.g. , ;

Hence, by the definition of Big-Omega.

Q.E.D.

2. Prove / Disprove:

Let ;

For c = 1, , where ;

Hence, , e.g. , ;

Hence, by the definition of Big-Omega.

Q.E.D.

3. Prove / Disprove:

Premise:

;

Statement:

, i.e. ;

Disproof:

To prove the given statement is to prove:

;

Take arbitrary positive real constant , if the given statement is true:

, i.e, ;

Hence contradicts with the case ,

given all positive real constant such that .

Hence, the statement , i.e. is NOT true;

Q.E.D.

Counter Example:

When , there exists no cases such that , i.e. .

4. Prove / Disprove:

Premise:

;

Statement:

, i.e. ;

Proof:

To prove the given statement is to prove:

;

Take arbitrary positive real constant , if the given statement is true:

, i.e,

by the definition of Little-Oh;

Take to be the smallest integer such that and ,

Hence, obviously, , , i.e, ;

Hence, , i.e. ,

Q.E.D.

5. Prove / Disprove:

Let ;

For , , where ;

Hence, , e.g. , , .

Hence, by the definition of Big-Theta.

Q.E.D.

6. Prove / Disprove:

Let ;

For c = 1, , where ;

Hence, , e.g. , ;

Hence, by the definition of Big-Omega.

Q.E.D.

7. Prove / Disprove:

Premise:

;

Statement:

, i.e. ;

Proof:

To prove the given statement is to prove:

;

Take arbitrary positive real constant , if the given statement is true:

, i.e,

by the definition of Little-Oh;

Take to be the smallest integer such that and ,

Hence, obviously, $n n_0 ^{}, , i.e, (f(n) cg(n))$;

Hence, , i.e. ,

Q.E.D. ### 8. Prove / Disprove: Premise:

;

Statement:

, i.e. ;

Proof:

To prove the given statement is to prove:

;

Take arbitrary positive real constant , if the given statement is true:

, i.e,

by the definition of Little-Oh;

As , ,

that is, it will grow bigger first, then grow smaller and eventually be smaller than c.

Hence, there exists an integer constant such that ;

Hence, , i.e. ,

Q.E.D.

Exercise 7

1. Given if is even, if is odd. Find the Big-Oh and Big-Omega behaviors of .

Suppose and ;

By the definition of Big-Oh:

;

Take ;

Hence: , when is even; when is odd;

Hence, , e.g. , ;

Hence, by the definition of Big-Oh.

Q.E.D.

By the definition of Big-Omega:

;

Take ;

Hence: , when is even; when is odd;

Hence, , e.g. , ;

Hence, by the definition of Big-Omega.

Q.E.D.