COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 6-2 : Asymptotic Notation 1
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Analysis of algorithms Asymptotic notation
Big-Oh,𝑂 ⋅
Coming next
Big-Omega, Ω(⋅) Big-Theta, Θ(⋅)
ANALYSIS OF ALGORITHMS
Often we are interested in knowing how much time an algorithm needs to perform a given task.
Typically, the time taken by an algorithm depends on the input and it grows with the size of such input. This is why we usually describe the running time of an algorithm with a function of the size of its input.
What do we mean by “size of input”? What do we mean by “running time”?
SIZE OF INPUT, RUNNING TIME
The notion of input size depends on the problem being studied, and it can therefore vary depending on the algorithm analyzed
It can be the number of elements in the input (e.g. the length of an array in a sorting algorithm)
It can be the number of bits required to represent the input (e.g. when multiplying two numbers)
It can be described by multiple numbers rather that one (e.g. algorithms that work with graphs)
The running time of an algorithm is the number of primitive operations (e.g. evaluating an expression, assigning a value, returning from a method,…) executed.
EXAMPLE – INSERTION SORT
Where 𝑡𝑖 is the number of times the condition of the while loop is checked for the specific 𝑖
insertionSort(list) {
for i from 1 to n-1 {
element = list[i]
k= i
while(k>0 && element46,whichmeans that −17𝑛+46<0 forall𝑛≥3
So we can take 𝒄 = 𝟖 and 𝒏𝟎 = 𝟑
OBSERVATIONS
Suppose𝑓𝑛 =𝑂(𝑔𝑛)then:
We can find multiple choices of constants to prove it. What
matters is that one choice exists.
These constants depend on 𝑓(𝑛). A different function belonging to 𝑂(𝑔 𝑛 ) would usually require different constants.
WHAT DOES 𝑂( 1 ) MEAN?
We say 𝑓 𝑛 is 𝑂(1), if there exist two positive constants
𝑛0 and 𝑐 such that, for all 𝑛 ≥ 𝑛0 ,
𝑓 𝑛 ≤ 𝑐.
So it just means that 𝑓 𝑛 is bounded by a constant.
BACK TO INSERTION SORT
At the beginning of today’s lecture we found the function describing the worst-case running time for insertion sort.
𝑇 𝑛 =𝑎𝑛2+𝑏𝑛+𝑐 𝑤𝑜𝑟𝑠𝑡
where 𝑎, 𝑏, and 𝑐 are some constants. 𝑎,𝑏 > 0,𝑐 < 0
Claim: 𝑇 𝑛 is 𝑂(𝑛2) 𝑤𝑜𝑟𝑠𝑡
𝑇 𝑛 IS𝑂(𝑛2)–PROOF 𝑤𝑜𝑟𝑠𝑡
𝑛 is𝑂𝑛2 Proof:𝑇 𝑛 =𝑎𝑛2+𝑏𝑛+𝑐
≤𝑎𝑛2 +𝑏𝑛2, forall𝑛≥𝟏(since𝑐 < 0) = 𝒂+𝒃𝑛2
Claim:𝑇 𝑤𝑜𝑟𝑠𝑡
𝑤𝑜𝑟𝑠𝑡
So we can take 𝒄′ = 𝒂 + 𝒃 and 𝒏𝟎 = 𝟏.
OBSERVATION ON WORST-CASE UPPER BOUNDS
When we use asymptotic notation with functions that represent the running time of an algorithm, we need to understand which running time we are referring to. Sometimes we might be interested in the worst-case running time, others in the running time no matter what the input is.
Since 𝑂-notation describes an upper bound, when we use it to bound the worst- case running time of an algorithm, then we have a bound on the running time of the algorithm on every input.
That is,
Since𝑇𝑛 ≤𝑇 𝑛,if𝑇 𝑛 =𝑂𝑔𝑛 ,then𝑇𝑛 =𝑂(𝑔𝑛) 𝑤𝑜𝑟𝑠𝑡 𝑤𝑜𝑟𝑠𝑡
HOW ELSE TO USE THE DEFINITION
We can also use the formal definition to prove that a function 𝑓(𝑛) is not 𝑂(𝑔 𝑛 ).
For example, 6𝑛3 ∉ 𝑂(𝑛2).
Proof (by contradiction): Suppose 6𝑛3 ∈ 𝑂(𝑛2). Then, by definition there exists two positive constants 𝑐 and 𝑛0 such that for all 𝑛 ≥ 𝑛0
6𝑛3 ≤𝑐⋅𝑛2 dividing both sides by 𝑛2 and by 6, we get
𝑛≤𝑐 6
which cannot possibly be true for arbitrarily large 𝑛.
TIGHT BOUNDS
Since Big O is an upper bound, if 𝑓(𝑛) is 𝑂(𝑛), then it is also 𝑂𝑛2 ,𝑂𝑛3 ,etc.
That is, 𝑂 𝑛 is a subset of 𝑂(𝑛2), which is a subset of 𝑂(𝑛3).
When we ask for a tight upper bound on 𝑓(𝑛) though, we want the simple function 𝑔(𝑛) such that 𝑂(𝑔 𝑛 ) is the smallest set that 𝑓(𝑛) belongs to.
FINAL GENERAL OBSERVATION
Never write 𝑂 3𝑛 , 𝑂( 5 𝑙𝑜𝑔2𝑛 ), etc.
Instead, write 𝑂 𝑛 , 𝑂(log𝑛), etc.
Why? The point of 𝑂-notation is to avoid dealing with constant factors. It is still technically correct to write the above. We just don’t do it.
In the next video: Big-Omega, Ω(⋅) Big-Theta, Θ(⋅)