COMP3600/6466 – Algorithms
Recurrence Analysis Cont. [CLRS sec. 4.Intro, 4.3 – 4.5]
Hanna Kurniawati
https://cs.anu.edu.au/courses/comp3600/ comp_3600_6466@anu.edu.au
A1
• Due: Monday, 17 Aug 23:59
• Grace period ends: Tuesday, 18 Aug 13:00
• Save as draft in wattle if you still want to reupload
Tutorials + Piazza 1
• How details should you be in analysing algorithms?
• If the question is to provide the exact function (e.g., 7a in A1), then you need to compute the exact functions, as what we discussed in week-1 (i.e., slide 26-29 of https://cs.anu.edu.au/courses/comp3600/week1- introduction-aftClass.pdf). You can use your own formatting, i.e., you don’t need to make a table and write per-line cost, etc., but you do need to provide similar level of details.
• If the question is to provide asymptotic bound, then you can be a bit more relaxed, as we are only interested in the asymptotic bound, not the exact running time function.
Piazza-2
• Functions & constants in asymptotic notations • Recall the definition, e.g.,
for Big-Oh 𝑂 𝑔 𝑛 = 𝑓 𝑛 ∃ 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑠 𝑐 𝑎𝑛𝑑 𝑛! 𝑠.𝑡.0≤𝑓𝑛 ≤𝑐𝑔𝑛 𝑓𝑜𝑟∀𝑛≥𝑛!}
Positive: number > 0.
Hence, both 𝑐 𝑎𝑛𝑑 𝑛! are > 0. Therefore, so is 𝑛.
Forthefunctions,bothvaluesof𝑓 𝑛 and𝑔 𝑛 are≥0forall𝑛. Therefore, by definition, they can be increasing/decreasing function
as long as the above is satisfied (e.g., #” satisfies the above
definition).
However, as per last week lecture (slide 38 of
https://cs.anu.edu.au/courses/comp3600/week2-asymptoticAnalysis- aftClass.pdf ), when the notations are applied for analysing algorithms, we can assume monotonically increasing functions
Piazza-3
• Asymptotic notations for functions with two parameters • Not that rare (e.g., Dijkstra complexity depends on #vertices
and #edges)
• Again recall the definition of an asymptotic notation, e.g., Big-Oh:
𝑂 𝑔 𝑛 = 𝑓 𝑛 ∃𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑠𝑐𝑎𝑛𝑑𝑛! 𝑠.𝑡.0≤𝑓𝑛 ≤𝑐𝑔𝑛 𝑓𝑜𝑟∀𝑛≥𝑛!}
• We can think of 𝑓 and 𝑔 with two-parameters (e.g., 𝑥 and 𝑦) , as the functions where the inputs are vectors,
e.g., 𝑛 = 𝑥 and 𝑛 = 𝑥! , and the definition remains. 𝑦 ! 𝑦!
• Though, membership test using limit will indeed become much harder.
Next, continuing from last week
Three Methods for Recurrence Analysis
• Substitution Method: Solving recurrences by guessing the form
• Recursion Tree: A more systematic way to guess the solution form
• Master Theorem: Finding asymptotic bound of a recurrence using a well-developed rules
Example
• This means the solution to the recurrence 𝑇 𝑛 = 2 𝑇 “# + 𝑛 𝑤 h 𝑒 𝑟 𝑒 𝑇 1 = 1
is asymptotically upper bounded by 𝑛 log 𝑛 Inotherwords,𝑇 𝑛 =𝑂 𝑛log 𝑛
How about the solution for MergeSort?
𝑇𝑛 =3Θ1 𝑖𝑓𝑛=1 𝑇”# +𝑇”# +Θ𝑛 𝑖𝑓𝑛>1
• Recall our sloppiness, we’ll convert the above to Θ 1 . 𝑖𝑓 𝑛 = 1
𝑇 𝑛 = 7 2 𝑇 𝑛2 + Θ 𝑛 𝑖 𝑓 𝑛 > 1 •WecanreplaceΘ𝑛 with𝑐$𝑛,andtheprevious
proof for 2𝑇 “# +𝑛 ≤ 𝑐𝑛log 𝑛 can be adjusted
slightlytoshow2𝑇 “# +𝑐$𝑛≤𝑐′𝑛log 𝑛 . • Please try!
Recall our solution to the recurrence
𝑇 𝑛 = 2 𝑇 !” + 𝑛 𝑤 h 𝑒 𝑟 𝑒 𝑇 1 = 1
• Basis step: Here, we’ll be sloppy
• For𝑛<2,𝑇 𝑛 =𝑐"
•𝑇2 =2𝑇1 +𝑐#2=2(𝑐"+𝑐#)≤2𝑐′log2 for𝑐′≥𝑐"+𝑐#
• Inductive hypothesis:
•Assumethat𝑇𝑘 ≤𝑐′𝑘log𝑘 for𝑘=2,3,...,𝑛
Recall our solution to the recurrence
𝑇 𝑛 = 2 𝑇 !" + 𝑛 𝑤 h 𝑒 𝑟 𝑒 𝑇 1 = 1
• Inductivestep:Proofthat𝑇 𝑛+1 ≤𝑐′ 𝑛+1 log 𝑛+1 𝑇 𝑛+1 =2 𝑐′!"#log!"# +𝑐! 𝑛+1
$$
≤𝑐′ 𝑛+1 log 𝑛+1 −log2 +𝑐! 𝑛+1
=𝑐′ 𝑛+1 log 𝑛+1 −1 +𝑐! 𝑛+1
=𝑐′ 𝑛+1 log 𝑛+1 −𝑐′ 𝑛+1 +𝑐! 𝑛+1 =𝑐′ 𝑛+1 log 𝑛+1 − 𝑐′−𝑐! 𝑛+1
≤𝑐′ 𝑛+1 log 𝑛+1 ∎
Note that we don’t need to put 𝑐$ ≥ 𝑐! as an assumption here, because in the basis step, we set 𝑐$ ≥ 𝑐! + 𝑐%
Would be useful to compare the above inductive step with the one for𝑇𝑛=2𝑇"# +𝑛in
https://cs.anu.edu.au/courses/comp3600/week2-recurrence- aftClass.pdf slide 23
Example: Reusing Other Results
• Solve the recurrence
𝑇𝑛=2𝑇 𝑛+log𝑛
• We want to transform the above recurrence into a recurrence we know the solution of. Suppose the recurrence we already know the solution is A, then we can use the recurrence solution of A, and then transform that solution into the solution of the above recurrence
Another Example
Let’s define 𝑚 = log 𝑛 .
Using base switch property of log, we have 𝑛 = 2$%& ' and
𝑛=2$%&'&# = 2'()" #
And,wecanrewrite𝑇 𝑛 as:𝑇 2( =2𝑇 2*# +𝑚 Let’salsodefine𝑆 𝑚 =𝑇 2( ,andrewrite𝑇 2( as:
𝑆 𝑚 = 2 𝑆 (" + 𝑚
Now, we know the solution to 𝑆 𝑚 , i.e., 𝑆 𝑚 = 𝑂(𝑚log𝑚)
Now, we need to replace those 𝑚 with log 𝑛, resulting in 𝑇 𝑛 =𝑇 2( =𝑆 𝑚 =𝑂(log𝑛.log log𝑛 )
Example: Need to be a bit careful
•Suppose 𝑇 𝑛 =𝑇 "# +𝑇 "# +1,andsuppose wewanttoguess𝑇𝑛 =𝑂(𝑛)
• Toshowtheabove,wewanttoshow𝑇 𝑛 ≤𝑐𝑛forsome positive constant 𝑐 and large 𝑛
𝑇 𝑛 = 𝑇 '" + 𝑇 '" + 1 = 𝑐𝑛 + 1
But,now,we’restuck...𝑇 𝑛 =𝑐𝑛+1 ≰𝑐𝑛
• The immediate fix would be change the guess to be of higher equivalent class (e.g., 𝑂(𝑛")). But, this would be looser bound.
• Instead,let’sshow𝑇 𝑛 =𝑂 𝑛 byshowing𝑇 𝑛 ≤𝑐𝑛−𝑑
Example: Need to be a bit careful
• Wecanmaintain𝑇 𝑛 =𝑂 𝑛 byshowing𝑇 𝑛 ≤𝑐𝑛−𝑑 𝑇 𝑛 = 𝑇 '" + 𝑇 '" + 1
=𝑐 𝑛2 −𝑑+𝑐 𝑛2 −𝑑+1
= 𝑐𝑛 − 2𝑑 + 1 ≤ 𝑐𝑛 − 𝑑
The above is true whenever 𝑑 ≥ 1
Three Methods for Recurrence Analysis
üSubstitution Method: Solving recurrences by guessing the form
• Recursion Tree: A more systematic way to guess the solution form
• Master Theorem: Finding asymptotic bound of a recurrence using a well-developed rules
What is Recursion Tree?
• Recursion Tree is a tree where
• Each node represents a single sub-problem along with
the cost of the particular sub-problem
• An edge from node a to node b means the sub-problem represented by node a calls the sub-problem represented by node b
• How to get total cost? Perform 2 sets of summations:
• Sum costs within each level to compute the per-level cost • Sum the per-level cost to compute the total cost
Recursion Tree Usage
• Usually, the total cost in recursion tree
becomes the guess for substitution method
• Therefore, a bit “sloppiness” is often fine. After all, the substitution method will verify
• We can also analyse exactly the total cost in recursion tree and use it as direct proof of the solution. But, in general, it can be a bit involved
• Master method, which we will cover next, is the result of such an analysis on several classes of functions
Example: Merge Sort
Cost per level 𝑐𝑛
𝑐𝑛
:
:
𝑐𝑛
Example: Merge Sort
Cost per level 𝑐𝑛
Total cost: 𝑐𝑛 log 𝑛 + 1
𝑐𝑛
:
:
𝑐𝑛
This is #levels. How to find it? Let’s denote tree depth: k,
where ! = 1
"! #
This means 𝑛 = 2 and 𝑘 = log 𝑛 .
Now, remember that #levels = depth + 1 = log𝑛 +1
Examples
•Solve𝑇 𝑛 =3𝑇 )* +Θ 𝑛# where𝑇 1 =1 • Recurrence tree:
• Tree depth: 𝑘, where
" =1≡𝑛=4& ≡𝑘=log%𝑛
%+
• Cost per-level:
• Non-leaves level-𝑖 : , . 𝑐𝑛"
#-
• Leaves: #leaves X 1 = 3$%&+ '.1 = 𝑛$%&+ ,
• Total cost:
𝑇 𝑛 =∑(%&'!()*+ , !𝑐𝑛.+𝑐𝑛%&'!,
≤ ∑/ , ! 𝑐𝑛. + 𝑐𝑛%&'! , !"# +-
!"# +-
≤0(" +𝑐𝑛%&'!,
≤ +- 𝑐𝑛. +, .
= 𝑂(𝑛 )
• Note that since the recurrence 𝑇 𝑛 Θ(𝑛!), the above result 𝑇 𝑛 = 𝑂 𝑛! 𝑇𝑛 =Θ(𝑛!).
+* # $%
is at least means that
Examples
•Solvetherecurrence𝑇 𝑛 =𝑇 ) +𝑇 0) +𝑂 𝑛 //
• Tree depth (𝑘): the depth of the deepest leaf "1𝑛=1≡"1=#
,,'
≡𝑘=log#'=$%&# =2$%&, =log,𝑛
# $ % & "& 2 $ % & ' ,,##
• Total cost:
At most #levels X cost per level = 𝑐𝑛. log, 𝑛 = 𝑂(𝑛 log 𝑛)
#
Now, notice that this is a rough estimate because the recurrence tree here is not a perfect (binary) tree.
In this case, we use the rough estimate as a guess that the solution of 𝑇 𝑛 is 𝑂(𝑛 log 𝑛), and then use substitution method to show that it is correct.
•Useinductiontoshow𝑇𝑛 =𝑂(𝑛log𝑛) • Basis step:
• For𝑛<2,𝑇 𝑛 =𝑐
• 𝑇 2 =𝑇 # +𝑇 " +𝑐3.2=𝑐+𝑐+2𝑐3 ≤𝑐′′2log 2 for
,, 𝑐′′ ≥𝑐+𝑐′
• Inductive hypothesis
• Assume that 𝑇 𝑘 ≤ 𝑐33𝑘log 𝑘 for 𝑘 = 2,3,...,𝑛
• Inductive step
• Proofthat𝑇 𝑛+1 ≤𝑐′′ 𝑛+1 log 𝑛+1
𝑇 𝑛+1 =𝑇 𝑛+1 +𝑇 2(𝑛+1) +𝑐3 𝑛+1 33
≤𝑐33 𝑛+1log𝑛+1 +𝑐33 2(𝑛+1)log2(𝑛+1) +𝑐3 𝑛+1 3333
=𝑐33'4# log 𝑛+1 −log3 +𝑐33"('4#) log2+log 𝑛+1 −log3 3,,
+ 𝑛+1 X−7--$%&,−"7--$%&,+ , ,
≤𝑐′′(𝑛+1)log(𝑛+1)for𝑐3 ≤0.9𝑐′′àrecallthebasis𝑐′′ ≥𝑐+𝑐′
The requirement 𝑐$ ≤ 0.9𝑐′′ will be
satisfied when we set 𝑐 ≥ %$ &
+𝑐 𝑛+1
=(𝑛+1)log(𝑛+1) 7-- +"7--
"7-- $%& " , , , +𝑐′Y
−0.918 =𝑐′′(𝑛+1)log(𝑛+1)+ 𝑛+1 𝑐′′ ",−log3 +𝑐′
∎
Three Methods for Recurrence Analysis
üSubstitution Method: Solving recurrences by guessing the form
üRecursion Tree: A more systematic way to guess the solution form
• Master Theorem: Finding asymptotic bound of a recurrence using a well-developed rules
Master Theorem
• For several classes of recurrence relation,
Master Theorem provides a “manual”
• No need to derive the recurrence tree, someone has done it and we can use it
Master Theorem (def.: [CLRS] pp. 94)
•Supposewewanttosolve𝑇 𝑛 =𝑎𝑇 )8 +𝑓 𝑛 ,𝑎≥ 1,𝑏>1, “‘ canbe “‘ or “‘
•Then,𝑇𝑛 hasthefollowingasymptoticbounds (highly dependent on 𝑓 𝑛 )
1. If𝑓 𝑛 =𝑂 𝑛($%&.9)2: forsomeconstant𝜖>0,then𝑇 𝑛 = Θ 𝑛$%&. 9
2. 𝑓 𝑛 =Θ 𝑛$%&.9 ,then𝑇 𝑛 =Θ 𝑛$%&.9log 𝑛 Amoregeneralformofcase-2:𝑓 𝑛 =Θ 𝑛$%&.9 log 𝑛 1 ,
for𝑘≥0,then𝑇 𝑛 =Θ 𝑛$%&.9 log 𝑛 14#
3. If𝑓 𝑛 =Ω 𝑛($%&.9)4: forsomeconstant𝜖>0andif 𝑎𝑓 “. ≤𝑐𝑓 𝑛 forsomeconstant𝑐<1and𝑛>𝑛!,then 𝑇𝑛=Θ𝑓𝑛
Examples
• Can we solve the following recurrences using Master Theorem? If we can, what’s the solution?
• 𝑇 𝑛 = 2 𝑇 “# + 𝑛
Here,𝑎=2,𝑏=2,𝑓 𝑛 =𝑛.Hence,𝑛()*8+ =𝑛.
Therefore, case-2 of Master Theorem applies, and𝑇 𝑛 =Θ(𝑛log𝑛).
Examples
• Can we solve the following recurrences using Master Theorem? If we can, what’s the solution?
• 𝑇 𝑛 = 2 𝑇 “# + 𝑛
• 𝑇 𝑛 = 3 𝑇 “% + 𝑛 l o g 𝑛
• 𝑇 𝑛 = 3 𝑇 “% + 𝑛 l o g 𝑛 Here,𝑎=3,𝑏=4,𝑓 𝑛 =𝑛log 𝑛 .
Notice that 𝑛$%&. 9 = 𝑛$%&+ , ≈ 𝑛!.<=", which means 𝑓 𝑛 = 𝑛log 𝑛 =Ω 𝑛$%&+,4: for𝜖≈0.2
Therefore, we look into case-3 of Master Theorem and check if𝑎𝑓 ". ≤𝑐𝑓 𝑛 forsomeconstant𝑐<1and𝑛>𝑛!
𝑎𝑓 “. =3’>log ‘> =,>𝑛 log𝑛−log4 =,>𝑛log𝑛−,”𝑛≤ 𝑐𝑓 𝑛 for𝑐=,> andanypositive𝑛
Therefore, based on case-3 of Master Theorem, 𝑇 𝑛 = Θ(𝑛 log 𝑛)
Examples
• Can we solve the following recurrences using Master Theorem? If we can, what’s the solution?
• 𝑇 𝑛 = 2 𝑇 “# + 𝑛
• 𝑇 𝑛 = 3 𝑇 “% + 𝑛 l o g 𝑛 • 𝑇 𝑛 = 2 𝑇 “# + 𝑛 l o g 𝑛
• 𝑇 𝑛 = 2 𝑇 bc + 𝑛 l o g 𝑛 Here,𝑎=2,𝑏=2,𝑓 𝑛 =𝑛log 𝑛 .
Since 𝑛$%&. 9 = 𝑛$%&# ” = 𝑛, it is tempted to use case-3 because𝑓 𝑛 =𝑛log 𝑛 =Ω 𝑛 .
However, case-3 can’t be use in this case because although 𝑓 𝑛 = 𝑛 log 𝑛 is asymptotically larger than 𝑛, it is not
polynomially larger, i.e., if we take ‘ $%& ‘ = log 𝑛 then log 𝑛 will ‘:
always be asymptotically lower than any polynomial 𝑛 for 𝜖 > 0, no matter how small 𝜖 is (you can check this by
showing lim ‘/ = ∞). Therefore, case-3 of Master Theorem ‘→@ $%& ‘
does not hold.
However, we can use the general form of case-2 with 𝑘 = 1
”
andhence,𝑇 𝑛 =Θ 𝑛 log 𝑛
Proof of Master Method?
• We’ll not cover the proof of Master method in this class
• But if you’re interested, please read them
in [CLRS] sec. 4.6
• The recurrence tree and summation of sequences we’ve covered so far should enable you to follow the proof
Three Methods for Recurrence Analysis
üSubstitution Method: Solving recurrences by guessing the form
üRecursion Tree: A more systematic way to guess the solution form
üMaster Theorem: Finding asymptotic bound of a recurrence using a well-developed rules
Next: Probabilistic Analysis