COMP3600/6466 – Algorithms
Asymptotic Analysis Part 1 [CLRS sec. 3.1]
Hanna Kurniawati
https://cs.anu.edu.au/courses/comp3600/ comp_3600_6466@anu.edu.au
What is Asymptotic Analysis?
• In general: Asymptotic analysis means understanding the behavior of a function in the limit
• In this class: Asymptotic analysis means understanding how the running time (or memory consumption) of an algorithm increases with the size of the input in the limit –that is, when the input size increases without bound
Asymptotic Analysis of Algorithms
• Recall: An algorithm transforms input to output
• Intuitively, asymptotic analysis of an algorithm means finding a function that maps input size to the required computational resources (time/memory) for the algorithm to transform the input to the desired output
• In this analysis, we are interested in the trend of the growth in computational resources rather than the exact function
• They are easier to work with & sufficient
• Therefore, the functions we are interested in this analysis are essentially bounds of the actual requirements
• Upper bound, lower bound, upper & lower bound
Why bother?
• In general, algorithms and computer programs are not for a single input, but for solving problems with varying input
• Asymptotic analysis helps in:
• Deciding which algorithms are better for solving a
specific problem
• Predicting time & memory requirements as input size grow. This could relate to the computers we need to purchase (the highest spec is not always the best, esp. when starting a business w. limited funding)
Asymptotic notations: Big-Oh 𝑂 𝑔 𝑛 Def.:
𝑂 𝑔 𝑛 = 𝑓 𝑛 ∃𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑠𝑐𝑎𝑛𝑑𝑛! 𝑠.𝑡.0≤𝑓𝑛 ≤𝑐𝑔𝑛 𝑓𝑜𝑟∀𝑛≥𝑛!}
Intuitively:
𝑂 𝑔 𝑛 is a set of functions that is upper bounded by a constant multiplication of 𝑔 𝑛 for “large” 𝑛 –that is, whenever 𝑛 ≥ 𝑛!.
Wewrite𝑓 𝑛 =𝑂 𝑔 𝑛 tomean𝑓 𝑛 ∈𝑂 𝑔 𝑛 ,andcall 𝑔 𝑛 to be an asymptotic upper bound of 𝑓 𝑛
This bound can be tight or not tight. The function 𝑔 𝑛 is an asymptotically tight upper bound of 𝑓 𝑛 whenever for ∀ 𝑛 ≥ 𝑛!, 𝑓 𝑛 is equal to 𝑔 𝑛 to within a constant factor
Visually,
Taken from: [CLRS] Figure 3.1
Is this information useful?
• The running-time complexity of an algorithm is at least 𝑂 𝑛:
Is this information useful?
• The running-time complexity of an algorithm is at least 𝑂 𝑛:
• No. Because 𝑂 𝑛: includes constant and even zero function. Stating “the running- time complexity of an algorithm is at least 𝑂 𝑛: ” can mean “the running-time complexity of an algorithm is at least epsilon or zero”, which does not provide any information.
Membership test for Big-Oh 𝑂 𝑔 𝑛 •Howtofigureoutif𝑓 𝑛 ∈𝑂 𝑔 𝑛 ?
• Find the constants 𝑐 and 𝑛! • Use limit
•𝑓 𝑛 ∈𝑂 𝑔 𝑛 means𝑓 𝑛 hassmallerorequalgrowth rate, compared to 𝑔 𝑛
•𝑓 𝑛 hassmallergrowthratethan𝑔 𝑛 means lim % ” =0 “→$ & ”
•𝑓 𝑛 hasthesamegrowthrateas𝑔 𝑛 means lim % ” =𝑐′
for a positive constant 𝑐′ “→$ & ” • Examples:
2𝑛?𝑂𝑛;2𝑛?𝑂𝑛’ ;2𝑛’?𝑂𝑛;2𝑛’?𝑂𝑛’
Membership test for Big-Oh 𝑂 𝑔 𝑛 •Howtofigureoutif𝑓 𝑛 ∈𝑂 𝑔 𝑛 ?
• Find the constants 𝑐 and 𝑛! • Use limit
•𝑓 𝑛 ∈𝑂 𝑔 𝑛 means𝑓 𝑛 hassmallerorequalgrowth rate, compared to 𝑔 𝑛
•𝑓 𝑛 hassmallergrowthratethan𝑔 𝑛 means lim % ” =0 “→$ & ”
•𝑓 𝑛 hasthesamegrowthrateas𝑔 𝑛 means lim % ” =𝑐′
for a positive constant 𝑐′ “→$ & ” • Example:
2𝑛=𝑂 𝑛 ;2𝑛=𝑂 𝑛’ ;2𝑛’≠𝑂 𝑛 ;2𝑛’=𝑂 𝑛’
Just in case…
• How to compute the limit? • lim “() = $ = 𝑢𝑛𝑑𝑒𝑓𝑖𝑛𝑒𝑑!!!
“→$ “!() $
• Recall L’Hopital’s rule: lim % ” = lim %” ” “→$ & ” “→$ &” ”
Examples
•Is8!=𝑂2! ?
• Is 𝑙𝑜𝑔 2𝑛 = 𝑂 𝑙𝑛 𝑛 ?
Examples
•Is8!=𝑂2! ?
No.Because:8″=2*” and lim ‘# $ = lim 2″ ‘ =∞
Therefore, 8″ ≠ 𝑂 2″ • Is 𝑙𝑜𝑔 2𝑛 = 𝑂 𝑙𝑛 𝑛 ?
Yes. Because:
𝑙𝑜𝑔2𝑛 =𝑙𝑜𝑔2 +𝑙𝑜𝑔𝑛 =𝑐)++”” =𝑐)+𝑐’𝑙𝑛𝑛 +” ‘
“→$ ‘# “→$
, (, +” ” &!
And using L’Hopital rule, lim % ! = lim # = 𝑐
“→$+”” “→$#% ‘ Therefore, 𝑙𝑜𝑔 2𝑛 = 𝑂 𝑙𝑛 𝑛
Next: Four other Asymptotic Notations