CMSC 435 ALGORITHM ANALYSIS & DESIGN

CMSC 435 ALGORITHM ANALYSIS & DESIGN

Lecture # 1

Mathematical Preliminaries

1. Big-O Notation

Definition: Let f(n) and g(n) be any two functions defined on the set of natural numbers. We say that

f(n) = O(g(n)) if there exist consants c and N₀, where c is a real number greater than 0 and N₀ is an

element of the set of natural numbers, such that for all n ³ N₀ f(n) < cg(n).

Illustration:

The above graph illustrates the meaning of f(n) = O(g(n)). The function g(n) grows

asymptotically as fast or faster than f(n). For all n > N₀ the value of cg(n) > f(n).

As shown in the illustration, it is not necesarily true that cg(n) is greater than f(n) for

all values for which these functions are defined, but for all values beyond an initial N₀.

It is also not necessary for N₀ to be the first value for which the inequality is true.

2. Application of Big-O notation to algorithm analysis

Consider selection sort.

void SelectionSort(int A[], int n) {

int i = 0;

while (i < n - 1) {

int j = i + 1;

while (j < n) {

if (A[j] < A[i])

swap(A[j], A[i])

j++;

}

i++;

}

How many times is the comparison if (A[i] < A[j]) executed?

In the first iteration of the outer loop, j takes on the values from 1 to n-1 -- there are n-1

comparisons performed. In each subsequent iteration, i is incremented by 1 and there

is one fewer comparison in the inner loop. The total number of comparisons is therefore

the sum:

n-1

f(n) = (n-1) + (n-2) + (n-3) + ....+ 1 = å k

k=1

where f(n) is the number of compares as a function of the size of the list n.

We claim that f(n) = O(n²).

Proof:

If f(n) = O(n²), then there exist constants c, N₀ such that f(n) < cn² for all n ³ N₀.

Choose c = 2, N₀ = 4. This choice is not unique, but we just have to find any pair

of c, N such that the definition is satisfied. Let's try this pair!

n-1

å k < 2n² for all n ³ 4.

k=1

Prove by induction.

Base case: n = 4

å k = 1 + 2 + 3 = 6 < 2n² = 2*4² = 32 True.

k=1

Inductive hypothesis: Assume P(n) is true --the statement for size n is true--

Show that then P(n+1) is true.

n-1

P(n): å k < 2n² for all n ³ 4. assumed true

k=1

P(n+1): å k < 2(n+1)² for all n ³ 4.

k=1

n-1

= å k + n < 2n² + n < 2n² + 4n + 2 = 2(n+1)² .

k=1

Since the comparison is the statement in the algorithm that is executed most frequently, and

the number of times it is called as a function of n is shown to be O(n²), we have shown that

selection sort is O(n²).

Example 2: Show that Towers of Hanoi is O(2ⁿ)

Let T(n) = the number of disk moves to move a tower of size n.

To move a tower of size n from peg 1 to peg 3 you first move a tower of size n-1

from peg 1 to peg 2, then move a disk from peg 1 to peg 3, and finally move the

tower of size n-1 from peg 2 to peg 3. The number of disk moves (T(n)) is the number

of moves to move the tower of size n-1 (T(n-1)) twice plus the single disk move.

T(n) = 2 T(n-1) + 1 where T(1) = 1

To prove that T(n) is O(2ⁿ), we must show that for a particular choice of c and N_0,

T(n) < c(2ⁿ-2) for all n ³ N₀ {since any function 2ⁿ - k is also O(2ⁿ)

--We need to strengthen the claim in order to prove

the result --

Choose c= 3 and N₀= 2.

Base case: n = 2

T(2) = 2T(1) + 1 = 3 < c(2ⁿ-2) = 3 (2²-2) = 6 True.

Inductive hypothesis: Assume P(n) is true --the statement for size n is true--

Show that then P(n+1) is true.

P(n): T(n) < 3(2ⁿ-2)

P(n+1): T(n+1) < 3(2ⁿ⁺¹-2)

T(n+1) = 2T(n) + 1 < 2* 3(2ⁿ-2) + 1 = 3(2ⁿ⁺¹-4) + 1

= 3(2ⁿ⁺¹-2) -6 + 1 < 3(2ⁿ⁺¹-2)

Example 3: Show that the fibonacci sequence

f(n) = f(n-1) + f(n-2) where f(0) = 0 and f(1) = 1

is big-O of 2ⁿ.

Find a pair of constants c and N₀ such that

f(n) < c2ⁿ for all n ³ N₀.

Choose c = 1 and N₀ = 2 and prove by induction.

Base case: f(2) = f(1) + f(0) = 1 + 0 = 1 < 2² True

Inductive hypothesis: Assume P(n) is true --the statement for size n is true--

Show that then P(n+1) is true.

P(n): f(n) < 2ⁿ for all n ³ 2 assumed true

P(n+1): f(n+1) < 2ⁿ⁺¹ for all n ³ 2

f(n+1) = f(n) + f(n-1) < 2f(n) < 2(2ⁿ) = 2ⁿ⁺¹

3. Big-W and Big-Q

Just as Big-O defines an asymptotic ceiling on the growth of a function, Big-W defines and asymptotic

floor.

Definition: Let f(n) and g(n) be any two functions defined on the set of natural numbers. We say that

f(n) = W(g(n)) if there exist consants c and N₀, where c is a real number greater than 0 and N₀ is an

element of the set of natural numbers, such that for all n ³ N₀ f(n) > cg(n).

If there exist a pair of positive constants c₁ and c₂ such that for some N₀ f(n) < c₁ g(n) and f(n) > c₂ g(n)

for all n ³ N₀, then f(n) = Q(g(n)) and g(n) provides a tight asymptotic bound for the function

Illustration:

4. Properties of the sets O(f(n)) and Q(f(n))

Show that the set of functions Q(f(n)) is an equivalence class.

Let g(n) and h(n) be any two functions contained in Q(f(n)). Use the definition of big-Q to demonstrate that

the elements of this set are reflexive, transitive and symmetric under the relation big-Q.

Does big-O also form an equivalence class?

Show that the functions f(n) and T(n) that respectively count the number of compares in selection sort

and the number of moves in Towers of Hanoi are Q(n²) and Q(2ⁿ) respectively.

Demonstrate that the fibonacci sequence f(n) = f(n-1) + f(n-2) is not Q(2ⁿ).

We have already shown that f(n) = O(2ⁿ). We must now find constant c₁ and N₀' such that

f(n) > c₁2ⁿ for all n ³ N₀' then

f(n) = f(n-1) + f(n-2) > c₁2^n-1 + c₁2^n-2 ³ c₁2ⁿ

but c₁ factors out of this expression, therefore any constant that satisfies the base case will do

equally well (poorly). For the inductive hypothesis to be satisfied, we must have

2^n-1 + 2^n-2 ³ 2ⁿ

2^n-2(2 + 1) = 3* 2^n-2 < 2ⁿ contradiction! no pair of c₁, N₀ exist

5. Other useful mathematical formulae

Logarithms

y = lg(n) <=> n = 2^y

log of a product: lg(ab) = lg(a) + lg(b)

log of a quotient: lg(a/b) = lg(a) - lg(b)

log of unity: log_b(1) = 0 in any base b

lg(n!) = lg(n) + lg(n-1) +...+ lg(1) = å lg(i)

i=1

å lg(i) = Q(nlg(n))

i=1

proof:

å lg(i) = O(nlg(n))

i=1

The largest term in this sum is lg(n), and there are n terms in the sum. Therefore

å lg(i) < nlg(n) for all n ³ 2

i=1

Now show that å lg(i) = W(nlg(n))

i=1

n ën/2û n ën/2û

ålg(i) = å lg(i) + å lg(i) ³ å lg(i) + ën/2û lg(ën/2û) ³ ën/2û lg(ën/2û) (A)

i=1 i=1 i=ën/2û+1 i=1

since every term in the second sum (from i=ën/2û+1 to n) is greater than the largest term

in the first sum and the first sum contains all positive terms.

We can show that ën/2û > n/4 and therefore ën/2û lg(ën/2û) > n/4 lg (n/4)

This can be written n/4 lg(n) - n/4 lg(4) = n/4 lg(n) - n/2

Next we show that there exists a c and N₀ such that

n/4 lg(n) - n/2 > c nlg(n) for all n ³ N₀

choose c = 1/8, then we find if n/4 lg(n) - n/2 > n/8 lg(n) for some range of n?

Solving , we get n/8 lg(n) > n/2 when lg(n) > 4 or n > 2⁴ = 16. Choose N₀ = 16.

and since all of the inequalities in equations (A) above are in the direction ³, we have

shown that

å lg(i) = W(nlg(n))

i=1

Since ålg(i) = W(nlg(n))

i=1

and å lg(i) = O(nlg(n))

i=1

we have by definition that it is Q(n lg(n)).

6. Application -- Show that all sorting algorithms are W(nlg(n))

Given a list of n items, there are n! possible arrangements of these items.

Let each one of these arrangements be a leaf in a binary a binary tree with the original arrangement

as the root. Then the height of this (balanced) binary tree is lg(n!) and we have just seen that this

function is W(nlg(n)). The length of the path from the root to any one of the leaves can be no

shorter than a constant multiple of nlg(n), and no comparison sorting algorithm can do better than this

number of compares.

Note we use the weaker claim that lg(n!) = W(nlg(n)) rather than the stronger statement that it is

Q(nlg(n)) because no comparison sorting algorithm can do better than the minimum number of

compares to go from the root to the appropriate leaf of the sorting tree, but not all sorting algorithms

will be this efficient.