Introduction
Computational Problem Solving
Problems
Designing solution strategies
Developing algorithms (iterative and recursive)
Writing algorithms that implement the strategies
Understand existing algorithms and modify/reuse
Understanding an algorithm by simulating its operation on an input
Checking/proving correctness
Analyzing and comparing performance: complexity or efficiency
Theoretically: Using a variety of mathematical tools
Empirically: Code, run and collect performance data
Choosing the best
1
Complexity Analysis of Recursive Algorithms
Chapter 4: OMIT 4.2 & 4.6
Keep up with the reading assignments!
3
Why can’t we use the complexity calculation technique that we have been discussing for non-recursive algorithms?
4
5
Because of recursion!
Fibonacci numbers: F0 = 1; F1 = 1; Fn = Fn-1+Fn-2
Fib (n: non-negative integer)
1 if n=0 or 1 then return 1
2 else return Fib(n-1)+Fib(n-2)
So what do we do?
Develop a pair of equations (called “recurrences” or “recurrence relations”) that characterize the behavior of a recursive algorithms and
Solve those to obtain the algorithm’s complexity.
6
Recurrences
What are these?
A pair of equations giving T(n) of recursive algorithms in terms of the
cost of recursive calls
and the cost of other steps
Step 1: Develop Recurrence Relations
How?
Determine what the base case(cases) is (are).
Determine steps that will be executed when the input size matches the base case(s).
Calculate the complexity of those steps.
Write the first part of the RR as T(base case input sizes) = what you calculated
8
Step 1: Develop Recurrence Relations
How?
Determine steps that will be executed when the input size is n, different from the base case(s).
Determine how many recursive calls (and with what input size in relation to the original input size of n) will be made.
Calculate the complexity of all other steps, excluding the recursive calls.
Write the second part of the RR as T(n) = T(input size for first recursive call) + T(input size for next recursive call) +…+complexity of all other steps.
9
10
Recursive algorithm example
T(n)= 4 = Θ(1) when n < 2
T(n)=T(n-1)+T(n-2)+7 =T(n-1)+T(n-2)+ Θ(1) when n≥2
Fib (n: non-negative integer)
1 if n=0 or 1 then return 1
2 else return Fib(n-1)+Fib(n-2)
11
Divide & Conquer Algorithm
A recursive algorithm that
divides the input each time into non-overlapping parts & apply itself to these smaller inputs until the base case is reached, and then
recursively combines the subproblem solutions to obtain a solution to the overall problem
Example: Merge Sort
Divide & Conquer Algorithm
Find-Max-Recursive(A:array[i…j] of numbers)
if i=j then return A[i]
else
mid=floor((i+j)/2)
return max(Find-Max-Recursive(A[i…mid), Find-Max-Recursive(A[mid+1…j])
Thinking Assignments
understand this algorithm
is it correct? can you prove it? how?
can you draw a recursion tree for A=[1,0,-5,7,23]?
develop its recurrences
12
13
General form of divide-and-conquer algorithm recurrences
D & C Algorithms
Recursion tree method can be used to solve these kinds of recurrences, like we did for Merge Sort
14
Reading Assignment
Section 4.1
understand the maximum subarray problem
understand the divide and conquer solution
understand FIND-MAX-CROSSING-SUBARRAY
simulate it on some specific arrays using paper and pen
understand FIND-MAXIMUM-SUBARRAY
draw the recursion tree for some specific arrays
understand its recurrences (equations 4.7)
Thinking Assignment: do exercise 4.1-1
come to next class with questions/confusions
other than answering your questions, this section will not be discussed in class
15
Solving Recurrences
Recursion-tree method (4.4)
Substitution method (4.3: omit “changing variables”)
Master method (4.5)
Backward substitution method (not in text)
Forward substitution method (not in text)
Reading Assignments: 4.3, 4.4, 4.5
16
Recurrence relations of Merge Sort
17
18
Analysis of Merge Sort
19
Suppose a divide-and-conquer algorithm has these recurrences
Another Example
20
Recursion-tree method
21
22
23
The cost of the entire tree
Alternate solution using finite summation result
24
25
The substitution method
The substitution method for solving recurrence entails two steps:
1. Guess the form of the solution.
2. Use mathematical induction to find the constants and show that the solution works.
3. If the inductive step of the proof fails, your guess is probably wrong.
26
How do you guess?
(1) If a recurrence is similar to one you have seen, guess a similar solution.
(2) Draw the recursion tree to get an approximate idea of what the solution might be.
(3) Trial and error.
27
Example of (1)
Guess
Now show using induction:
28
Base case
However,
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
29
Now Assume
We have to show
30
Guess a solution using the recursion tree method approximately
Then prove that it is correct
Example of (2)
31
32
We need to prove by induction that
Base case
Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
33
Now Assume
We have to show
34
Subtleties
Example of (3): Trial and error: correct guess; fixable problem with proof
Guess
Show
Base Case:
Assume
Inductive Step: proof fails
35
Instead, show
Base case:
Assume
Then
This technique can be used if the inductive step fails due to a constant additive or subtractive term
36
Example of (3): Trial and error (wrong guess)
Avoiding pitfalls
Guess
Works for the base case: T(1)=1 ≤ c*1when c≥1
Show
Assume
You cannot find such a positive constant.
This is an example of inductive proof failure suggesting that your guess is WRONG
37
Another example
(for you to read and understand)
T(n)=3T(n/4) + cn2, T(1) = c
Guess T(n)=O(n2)
We want to show that T(n) ≤ dn2 for some constant d > 0. Works for the base case (why?) . So assume T(n/4) ≤ d(n/4)2
38
Changing variables method
omit
To deal with recursive call input sizes that are square roots, cube roots and powers of n less than 1
39
The master method
No need to memorize
Learn how to apply
The Master Theorem
If T(n)=aT(n/b) + f(n) (and T(base case)=some constant) and a and b are constants, then:
40
41
42
43
44
45
When master method doesn’t apply
omit
The master method does not apply to the recurrence
even though it has the proper form: a = 2, b=2, f(n)= n lgn, and
It might seem that case 3 should apply, since f(n)= nlgn is asymptotically larger than
The problem is that it is NOT polynomially larger, i.e., not larger by a term nε.
46
Method of backward substitutions
Start with the recurrence relation for T(n), and
repeatedly expand its right hand side by substituting for the T terms.
After several such expansions, look for and find a pattern that allows you to express T(n) as a closed-form formula.
If such a formula is evident, check its validity by direct substitution into the recurrence relations.
47
T(n)=T(n-1)+n; T(0)=1
T(n-1)=T(n-2)+(n-1)
So T(n)=T(n-2)+n+(n-1)
T(n-2)=T(n-3)+(n-2)
So T(n)=T(n-3)+n+(n-1) +(n-2)
T(n-3)=T(n-4)+(n-3)
So T(n)=T(n-4)+n+(n-1) +(n-2)+(n-3)
Eventually, T(n)=T(n-n)+n+(n-1) +(n-2)+(n-3)+
…+(n-(n-1))=T(0)+n+(n-1)+(n-2)+(n-3)+…+1= 1+ n(n+1)/2
Check:
LHS of recurrence T(n) = 1+ n(n+1)/2 = n2/2+n/2+1
RHS = T(n-1) + n = 1+ (n-1)n/2 + n = n2/2+n/2+1
48
Method of forward substitutions
Start with the recurrence relation for T(base case), and repeatedly calculate non-base cases, e.g., T(1), T(2) etc. After several such calculations, look for and find a pattern that allows you to express T(n) as a closed-form formula. If such a formula is evident, check its validity by direct substitution into the recurrence relations.
49
T(n)=T(n-1)+1; T(0)=1
T(1)=T(0)+1=1+1=2
T(2)=T(1)+1=2+1=3
T(3)=T(2)+1=3+1=4
T(4)=T(3)+1=4+1=5
T(5)=T(4)+1=5+1=6
…
T(n)=n+1
Check:
LHS = T(n) = n+1
RHS = T(n-1)+1 = n+1
50
Complexity of Recursive Algorithms
First develop the recurrences from the algorithm
Then solve them using the most appropriate method
How do you know which method to apply?
Substitution method: generally applicable
Recursion tree method and Master method: for Divide and Conquer algorithms that reduce inputs by a fixed factor
Backward/Forward substitution method: for algorithms that reduce input by a constant amount
51
Summary
We have discussed several tools and techniques for mathematically determining the complexity of algorithms:
For non-recursive algorithms, calculate T(n) by adding up the (cost * # of executions) of each step
For recursive algorithms, develop the recurrence relations and solve them using a variety of techniques to obtain T(n)
Once you obtain an exact expression for T(n) [or through various approximations an upper or lower bound for T(n)] as a function of n, then you can determine the order of complexity of the algorithm.
52
Empirical Complexity
Another approach is to determine T(n) by plotting it as a graph of actual time taken by the algorithm versus input size by:
Coding the algorithm in a programming language
Randomly generating inputs of different sizes: typically from small sizes up to 100K’s or millions
Running the program on each of these inputs and measuring the time taken using the system clock
Plotting time against input size
Determining the appropriate g(n) that fits this graph or provides an upper or lower bound (see next slide for examples of g(n))
This function g will then give you the order of complexity of the algorithm
53
54
1 1 1 1 1 1 1 1 1 1 loglogn 0 0.66444870745389994 1 1.2153232957367781 1.37014335194601 1.489211469238126 1.5849625007211561 1.6644487074538901 1.732020845644618 1.7905350238931339 logn 1 1.5849625007211561 2 2.3219280948873622 2.5849625007211601 2.8073549220576042 3 3.169925001442337 3.3219280948873631 3.4594316186372982 n 2 3 4 5 6 7 8 9 10 11 nlogn 2 4.7548875021634647 8 11.60964047443681 15.50977500432694 19.651484454403231 24 28.529325012980809 33.219280948873632 38.053747805009998 n-squared 4 9 16 25 36 49 64 81 100 121
î
í
ì
+
£
Q
=
otherwise
n
f
b
n
aT
c
n
if
n
T
)
(
)
/
(
)
1
(
)
(
î
í
ì
>
+
=
=
1
)
2
/
(
2
1
)
(
n
if
cn
n
T
n
if
c
n
T
T
n
if
n
T
n
n
if
n
(
)
(
)
(
/
)
(
)
=
=
+
>
ì
í
î
Q
Q
1
1
2
2
1
)
log
(
log
)
(
n
n
cn
n
cn
n
T
Q
=
+
=
ë
û
î
í
ì
Q
+
=
Q
=
otherwise
n
n
T
n
if
n
T
)
(
)
4
/
(
3
1
)
1
(
)
(
2
ë
û
î
í
ì
+
=
=
otherwise
cn
n
T
n
if
c
n
T
2
)
4
/
(
3
1
)
(
(
)
(
)
(
)
)
(
)
(
,
)
(
.
.
)
(
13
16
)
16
/
3
(
1
1
16
3
16
3
)
(
2
3
log
2
3
log
2
3
log
2
0
1
log
0
3
log
2
4
4
4
4
4
n
o
n
T
so
polynomial
quadratic
a
n
T
e
I
n
cn
n
cn
n
cn
n
cn
n
T
i
i
n
i
i
=
<
Q
+
=
Q
+
-
=
Q
+
÷
ø
ö
ç
è
æ
<
Q
+
÷
ø
ö
ç
è
æ
=
å
å
¥
=
-
=
ë
û
T
n
T
n
n
T
(
)
(
/
)
(
)
=
+
=
ì
í
î
2
2
1
1
)
log
(
)
(
n
n
O
n
T
=
n
cn
n
T
log
)
(
£
?
0
1
log
1
)
1
(
1
=
£
=
c
T
)
2
if
(
2
2
log
2
)
2
(
4
³
=
£
=
c
c
c
T
ë
û
ë
û
ë
û
T
n
c
n
n
(
/
)
/
log
/
2
2
2
£
ë
û
ë
û
)
1
(if
log
)
1
(
log
2
log
log
2
log
)
2
/
log
2
/
(
2
)
(
.
c
n
cn
c
n
n
cn
n
cn
n
cn
n
n
cn
n
n
n
c
n
T
³
£
-
-
=
+
-
=
+
£
+
£
2
)
2
(
=
T
cn
n
T
n
T
n
T
+
+
=
)
3
/
2
(
)
3
/
(
)
(
)
1
if
(
2
2
log
2
)
2
(
2
³
=
£
=
d
d
d
T
n
dn
n
T
log
)
(
£
)
3
/
log(
)
3
/
(
)
3
/
(
n
n
d
n
T
£
)
3
2
3
/(lg
0
)
)
3
2
3
(lg
(
lg
)
)
3
2
3
(lg
(
lg
)
2
3
lg
3
2
3
lg
3
1
(
lg
))
2
/
3
lg(
(lg
3
2
)
3
lg
(lg
3
)
(
-
>
>
–
–
£
–
–
–
=
+
+
–
=
+
–
+
–
£
c
d
or
cn
dn
when
n
dn
cn
dn
n
dn
cn
dn
n
dn
cn
n
dn
n
dn
n
T
)
3
/
2
log(
)
3
/
2
(
)
3
/
2
(
n
n
d
n
T
£
ë
û
é
ù
1
)
1
(
;
1
)
2
/
(
)
2
/
(
)
(
=
+
+
=
T
n
T
n
T
n
T
)
(
)
(
n
O
n
T
=
2
/
)
2
/
(
cn
n
T
£
cn
cn
cn
cn
n
T
£
/
+
£
+
+
£
1
1
2
/
2
/
)
(
cn
n
T
£
)
(
1
1
*
1
)
1
(
least
at
is
c
when
c
T
£
=
ë
û
é
ù
T
n
T
n
T
n
(
)
(
/
)
(
/
)
=
+
+
2
2
1
1
)
(
)
(
)
(
–
£
Þ
=
cn
n
T
n
O
n
T
1
)
(
1
)
1
2
/
(
)
1
2
/
(
)
(
–
£
+
–
+
–
£
cn
n
T
cn
cn
n
T
1
2
/
)
2
/
(
–
£
cn
n
T
2
)
1
(
1
)
1
(
least
at
is
c
when
holds
c
T
–
£
=
ë
û
T
n
T
n
n
T
(
)
(
/
)
(
)
=
+
=
ì
í
î
2
2
1
1
)
(
)
(
n
O
n
T
=
T
n
cn
(
)
£
??
)
1
(
)
2
/
(
2
)
(
cn
c
n
n
cn
n
cn
n
T
£
+
=
+
£
+
£
2
/
)
2
/
(
cn
n
T
£
ë
û
ë
û
d
c
or
d
c
d
when
dn
c
d
n
cn
dn
cn
n
d
cn
n
d
cn
n
T
n
T
£
£
+
£
+
=
+
=
+
£
+
£
+
=
13
16
,
)
16
3
(
,
)
16
3
(
16
3
)
4
/
(
3
4
/
3
)
4
/
(
3
)
(
2
2
2
2
2
2
2
2
2
Tn T n n() ( )lg 2
Let
m nlg
.
T T m
m m
( ) ( )
/
2 2 2
2
Let
)2()(
m
TmS
)2/()2(
2/
mST
m
Then
Sm Sm m() (/) 2 2
.
Sm Om m
Tn T Sm Om m
O n n
m
() (lg )
() ( ) () (lg )
(lg lglg)
2
)
2
(
)
(
m
T
m
S
=
)
2
/
(
)
2
(
2
/
m
S
T
m
=
Let
.
Let
Then
.
_925211299.unknown
_925211400.unknown
_1232437688.unknown
_1232437773.unknown
_925211449.unknown
_925211331.unknown
_925211262.unknown
)
log
(
)
(
0
)
(log
(
)
(
:
1
)
n
n
a
a
b
b
n
T
then
for
O
n
f
if
Q
=
>
=
–
e
e
))
(
(
)
(
1
tan
)
(
)
/
(
0
)
(log
(
)
(
:
3
)
n
f
n
T
then
c
t
cons
some
for
n
cf
b
n
af
if
and
for
n
f
if
n
a
b
Q
=
<
£
>
W
=
+
e
e
)
lg
log
(
)
(
)
log
(
)
(
:
2
n
n
T
then
n
f
if
n
n
a
a
b
b
Q
=
Q
=
Tn Tn n() (/) 9 3
a b fn n
n n fn On
9 3
3 3
9
2
91
, ,()
, () ( )
log log
Case Tn n1
2
() ( )
Tn T n() ( /) 2 3 1
a b fn
n n fn
1, 32 1
1
32
1
0
/,()
(),
log
/
Case Tn n2 () (log )
·
·
_925234096.unknown
_925234284.unknown
_925234285.unknown
_925234286.unknown
_925234229.unknown
_925234054.unknown
Tn Tn n n() (/) log 3 4
)()(,
log)(,4,3
3log
793.0
3log
44
nnfnn
nnnfba
Case
af(n/b)= (
n
) (
n
)
n
n=cf(n)
c= n
Tn n n
3
3
4 4
3
4
3
4
Check
for and suffi ciently la rge
log log
,
() (log )
)
(
)
(
,
log
)
(
,
4
,
3
3
log
793
.
0
3
log
4
4
e
+
W
=
=
=
=
=
n
n
f
n
n
n
n
n
f
b
a
·
_925234530.unknown
_1231838525.unknown
_925234480.unknown
,
lg
)
2
/
(
2
)
(
n
n
n
T
n
T
+
=
.
log
n
n
a
b
=
.
log
n
n
a
b
=
/docProps/thumbnail.jpeg