CS483-04 Non-recursive and Recursive Algorithm

Analysis

Instructor: Fei Li

Room 443 ST II

Office hours: Tue. & Thur. 4:30pm - 5:30pm or by appointments

lifei@cs.gmu.edu with subject: CS483

http://www.cs.gmu.edu/∼ lifei/teaching/cs483_fall07/

CS483 Design and Analysis of Algorithms 1 Lecture 04, September 6, 2007

 Outline

➣ Review and More

➣ Analysis of Non-recursive Algorithms
➣ Analysis of Recursive Algorithms
➣ Examples

CS483 Design and Analysis of Algorithms 2 Lecture 04, September 6, 2007

 Review
ˆ O(g(n)) := {f (n) | there exist positive constants c and n0 such that 0 ≤ f (n) ≤ c · g(n)
for all n ≥ n0 }.

f (n) ∈ O(g(n))

f (n) grow no faster than g(n).

ˆ Ω(g(n)) := {f (n) | there exist positive constants c and n0 such that 0 ≤ c · g(n) ≤ f (n)
for all n ≥ n0 }.

f (n) ∈ Ω(g(n))

f (n) grows at least as fast as g(n).

ˆ Θ(g(n)) := {f (n) | there exist positive constants c1 , c2 , and n0 such that
c1 · g(n) ≤ f (n) ≤ c2 · g(n) for all n ≥ n0 }.

f (n) ∈ Θ(g(n))

f (n) grows at the same rate as g(n).

CS483 Design and Analysis of Algorithms 3 Lecture 04, September 6, 2007

 Asymptotic Notations

c2 g(n)
f (n)
c1 g(n)

n0 n
f (n) ∈ Θ(g(n))

cg(n)
f (n) f (n)
cg(n)

n0 n n0 n
f (n) ∈ O(g(n)) f (n) ∈ Ω(g(n))

CS483 Design and Analysis of Algorithms 4 Lecture 04, September 6, 2007

 Review

➣ Tools and techniques to get asymptotic notation

ˆ L’Hopital’s rule
If limn→∞ f (n) = limn→∞ g(n) = ∞ and the derivatives f ′ and g ′
exist, then

f (n) f ′ (n)
lim = lim ′
n→∞ g(n) n→∞ g (n)

ˆ Stirling’s formula

√ n
n! ≈ 2πn( )n
e
where e is the base of natural logarithm, e ≈ 2.718. π ≈ 3.1415.

CS483 Design and Analysis of Algorithms 5 Lecture 04, September 6, 2007

 Exercises

➣ All logarithmic functions loga n belong to the same class Θ(log n) no matter
what the logarithmic base a > 1 is.

➣ All polynomials of the same degree k belong to the same class

ak nk + ak−1 nk−1 + · · · + a1 n + a0 ∈ Θ(nk ).
➣ Exponential functions an have different orders of growth for different a’s, i.e.,
2n ∈
/ Θ(3n ).
➣
√
ln n < (ln n) < n < n < n · ln n < n2 < n3 < 2n < n! < nn
2

CS483 Design and Analysis of Algorithms 6 Lecture 04, September 6, 2007

 Some Properties of Asymptotic Order of Growth

➣ Transitivity
ˆ f (n) ∈ O(g(n)) and g(n) ∈ O(h(n)) ⇒ f (n) ∈ O(h(n))
ˆ f (n) ∈ Θ(g(n)) and g(n) ∈ Θ(h(n)) ⇒ f (n) ∈ Θ(h(n))
ˆ f (n) ∈ Ω(g(n)) and g(n) ∈ Ω(h(n)) ⇒ f (n) ∈ Ω(h(n))
➣ Reflexivity
ˆ f (n) ∈ O(f (n))
ˆ f (n) ∈ Θ(f (n))
ˆ f (n) ∈ Ω(f (n))
➣ Symmetry and Transpose Symmetry
ˆ f (n) ∈ Θ(g(n)) if and only if g(n) ∈ Θ(f (n))
ˆ f (n) ∈ O(g(n)) if and only if g(n) ∈ Ω(f (n))

CS483 Design and Analysis of Algorithms 7 Lecture 04, September 6, 2007

 Outline

➣ Review
➣ Analysis of Non-recursive Algorithms
➣ Analysis of Recursive Algorithms
➣ Examples

CS483 Design and Analysis of Algorithms 8 Lecture 04, September 6, 2007

 Time Efficiency of Non-recursive Algorithms

ˆ Decide on parameter n indicating input size.

ˆ Identify algorithm’s basic operation.
ˆ Determine worst, average, and best cases for input of size n.
ˆ Sum the number of basic operations executed.
ˆ Simplify the sum using standard formula and rules (see Appendix A).

CS483 Design and Analysis of Algorithms 9 Lecture 04, September 6, 2007

 Time Efficiency of Non-recursive Algorithms
Pu
ˆ i=l 1 = 1 + 1 + · · · + 1 = (u − l) + 1.
n2
Pn n(n+1)
ˆ i=1 i = 1 + 2 + · · · + n = 2 ≈ 2 ∈ Ω(n2 ).
n3
Pn n(n+1)(2n+1)
ˆ 2 2 2
i=1 i = 1 + 2 + · · · + n =
2
6 ≈ 3 ∈ Ω(n3 ).
Pn
ˆ i=1
i 2
a = 1 + a+ a + ···+ a = n an+1 −1
a−1 , ∀a 6= 1.

CS483 Design and Analysis of Algorithms 10 Lecture 04, September 6, 2007

 Example 1: Maximum Element

ˆ Determine the value of the largest element in a given array.

ˆ Input: An array A[0, · · · , n − 1] of real numbers.
ˆ Output: The value of the largest element in A.

Algorithm 0.1: M AX E LEMENT(A[0, · · · n − 1])

max = A[0]
for i = 1 to n − 1

if A[i] > max
do
 then max = A[i]

return (max)

CS483 Design and Analysis of Algorithms 11 Lecture 04, September 6, 2007

 Example 2: Element Uniqueness Problem

ˆ Determine whether all the elements in a given array are distinct.

ˆ Input: An array A[0, . . . , n − 1].
ˆ Output: Returns “true” if all the elements in A are distinct and “false”
otherwise.

Algorithm 0.2: U NIQUE E LEMENTS(A[0, · · · n − 1])

for i= 0 to n − 2


 for j = i + 1 to n − 1
 
do if A[i] = A[j]
 do 


then return (f alse)

return (true)

CS483 Design and Analysis of Algorithms 12 Lecture 04, September 6, 2007

 Example 3: Matrix Multiplication

ˆ Multiply 2 n-by-n matrices by the definition-based algorithm.

ˆ Input: 2 n-by-n matrices A and B .
ˆ Output: Matrix C = A · B .

Algorithm 0.3: M ATRIX M ULTI(A, B )

for i= 0 to n − 1



 for j = 0 to n − 1
 
C[i, j] = 0

 

do 


 do for k = 0 to n − 1

 

do C[i, j] = C[i, j] + A[i, k] · B[k, j]
 

return (C)

CS483 Design and Analysis of Algorithms 13 Lecture 04, September 6, 2007

 Example 4: Counting Binary Bits

ˆ Input: A positive decimal integer n.

ˆ Output: The number of binary digits in n’s binary representation.

Algorithm 0.4: C OUNT B INARY B ITS(n)

count = 1
while n>1

count = count + 1
do
n = ⌊n/2⌋

return (count)

CS483 Design and Analysis of Algorithms 14 Lecture 04, September 6, 2007

 Outline

➣ Review
➣ Analysis of Non-recursive Algorithms
➣ Analysis of Recursive Algorithms
➣ Examples

CS483 Design and Analysis of Algorithms 15 Lecture 04, September 6, 2007

 Recurrences

➣ A recurrence is an equation or inequality that describes a function in terms of

its value over a smaller value.

➣ Example: Find n!

CS483 Design and Analysis of Algorithms 16 Lecture 04, September 6, 2007

 Recurrences
➣ A recurrence is an equation or inequality that describes a function in terms of its value over a
smaller value.

➣ Example: Find n!
ˆ Non-recursive: 1 · 2 · 3···n

Algorithm 0.5: F IND FACTORIAL -α(n)

f actorial = 1
for i = 1 to n
do f actorial = f actorial · i
return (f actorial)

ˆ Recurrence: f (n) = n · f (n − 1)

CS483 Design and Analysis of Algorithms 17 Lecture 04, September 6, 2007

 Algorithm 0.6: F IND FACTORIAL -β (n)

if n =0
then return (1)

else return (n · FindFactorial − β(n − 1))

CS483 Design and Analysis of Algorithms 18 Lecture 04, September 6, 2007

 Example: Counting Number of Bits
ˆ Input: A positive decimal integer n.

ˆ Output: The number of binary digits in n’s binary representation.

Algorithm 0.7: N ON -R ECURSIVE C OUNT(n)

count = 1
while n>1
8
<count = count + 1
do
:n = ⌊n/2⌋

return (count)

Algorithm 0.8: R ECURSIVE C OUNT(n)

if i =1
do return (1)

else return (RecursiveCount(⌊n/2⌋) + 1)

CS483 Design and Analysis of Algorithms 19 Lecture 04, September 6, 2007

 Example: Fibonacci Numbers

ˆ Output: A sequence of numbers F0 , F1 , F2 , . . . , Fn , . . . such that

8
< Fn−1 + Fn−2 , if n >1
>
>
Fn = 1, if n =1
>
>
0, if n = 0.
:

CS483 Design and Analysis of Algorithms 21 Lecture 04, September 6, 2007

 Example: Fibonacci Numbers

ˆ Output: A sequence of numbers F0 , F1 , F2 , . . . , Fn , . . . such that

8
< Fn−1 + Fn−2 , if n >1
>
>
Fn = 1, if n =1
>
>
0, if n = 0.
:

Algorithm 0.9: F IB N UMBER(n)

if n =0
return (0)

if n =1
return (1)

else return (F ibN umber(n − 1) + F ibN umber(n − 2))

CS483 Design and Analysis of Algorithms 22 Lecture 04, September 6, 2007

 Example: Hanoi Tower Problem

ˆ Move all the disks from peg a to peg c. Large disk cannot be on top of a smaller one.

ˆ Input: n disks in order of sizes on peg a. 3 pegs a, b, and c

http://en.wikipedia.org/wiki/Tower_of_Hanoi

Algorithm 0.10: H ANOI TOWER(n, a, c, b)

if n =1
Move the disk from a to c
8
<HanoiTower(n − 1, a, b, c)
>
>
else Move the largest disk from a to c
>
>
HanoiTower(n − 1, b, c, a)
:

CS483 Design and Analysis of Algorithms 23 Lecture 04, September 6, 2007

 Analysis of Recursive Algorithms

➣ The iteration method

ˆ Expand (iterate) the recurrence and express it as a summation of terms
depending only on n and the initial conditions.

➣ The substitution method

➣ Master Theorem
(To be introduced in Chapter 4.)

CS483 Design and Analysis of Algorithms 24 Lecture 04, September 6, 2007

 Iteration Method: Examples

ˆ n!

T (n) = T (n − 1) + 1

ˆ Tower of Hanoi

T (n) = 2T (n − 1) + 1

CS483 Design and Analysis of Algorithms 25 Lecture 04, September 6, 2007

 Iteration: Example

ˆ n! (T (n) = T (n − 1) + 1)

T (n) = T (n − 1) + 1
= (T (n − 2) + 1) + 1
= T (n − 2) + 2
··· ···
= T (n − i) + i
··· ···
= T (0) + n = n

ˆ Tower of Hanoi (T (n) = 2T (n − 1) + 1) ???

CS483 Design and Analysis of Algorithms 26 Lecture 04, September 6, 2007

 Iteration: Example

ˆ n! (T (n) = T (n − 1) + 1)
ˆ Tower of Hanoi (T (n) = 2T (n − 1) + 1)

T (n) = 2T (n − 1) + 1
= 2(2T (n − 2) + 1) + 1
= 22 T (n − 2) + 2 + 1
··· ···
= 2i T (n − i) + 2i−1 + · · · + 1
··· ···
= 2n−1 T (1) + 2n−1 + 2n−1 + · · · + 1
n−2
X
n−1
= 2 T (1) + 2i
i=0

= 2n−1 + 2 n−1
−1
= 2n − 1

CS483 Design and Analysis of Algorithms 27 Lecture 04, September 6, 2007

 Assignment 1

➣ Problems
1. Prove or find a counter-example:
n n n n
( ) < n! < ( ) , if n ≥ 6.
3 2
2. p. 8, Exercises (1.1) 5, 6.

3. p. 60, Exercises (2.2) 5, 6

4. p. 67, Exercises (2.3) 2, 4

5. p. 76, Exercises (2.4) 1, 3, 5

➣ Due date: September 20, 2007. In class

CS483 Design and Analysis of Algorithms 37 Lecture 04, September 6, 2007