How to Win Coding Competitions: Secrets of Champions
Week 2: Computational complexity. Linear data structures
Lecture 1: Big O notation. Computational complexity
Pavel Krotkov
Saint Petersburg 2016
Function comparison
I consider two functions f (x) and g (x) defined on R
2/9
Function comparison
I consider two functions f (x) and g (x) defined on R
I how can we compare values of these functions?
2/9
Function comparison
I consider two functions f (x) and g (x) defined on R
I how can we compare values of these functions?
I some obvious ideas
I ∀x : f (x) = g (x)
I ∀x : f (x) < g (x)
I ∀x : f (x) > 2 × g (x)
2/9
Function comparison
I consider two functions f (x) and g (x) defined on R
I how can we compare values of these functions?
I some obvious ideas
I ∀x : f (x) = g (x)
I ∀x : f (x) < g (x)
I ∀x : f (x) > 2 × g (x)
We can’t introduce equivalence classes for functions based on these comparisons.
2/9
Asymptotical equivalence
Let’s find a way to introduce equivalence classes for functions.
3/9
Asymptotical equivalence
Let’s find a way to introduce equivalence classes for functions.
f (x) = Θ(g (x))
3/9
Asymptotical equivalence
Let’s find a way to introduce equivalence classes for functions.
f (x) = Θ(g (x))
(
∃c1 : ∀x > x0 : f (x) < c1 × g (x)
I ∃x0 :
∃c2 : ∀x > x0 : f (x) > c2 × g (x)
3/9
Asymptotical equivalence
Let’s find a way to introduce equivalence classes for functions.
f (x) = Θ(g (x))
(
∃c1 : ∀x > x0 : f (x) < c1 × g (x)
I ∃x0 :
∃c2 : ∀x > x0 : f (x) > c2 × g (x)
f is bounded above and below by g asymptotically
3/9
O and Ω
Now we can introduce two related notations.
4/9
O and Ω
Now we can introduce two related notations.
I f (x) = O(g (x))
4/9
O and Ω
Now we can introduce two related notations.
I f (x) = O(g (x))
I ∃x0 , c : ∀x > x0 : f (x) < c × g (x)
4/9
O and Ω
Now we can introduce two related notations.
I f (x) = O(g (x))
I ∃x0 , c : ∀x > x0 : f (x) < c × g (x)
I f is bounded above by g assymptotically
4/9
O and Ω
Now we can introduce two related notations.
I f (x) = O(g (x))
I ∃x0 , c : ∀x > x0 : f (x) < c × g (x)
I f is bounded above by g assymptotically
I f (x) = Ω(g (x))
4/9
O and Ω
Now we can introduce two related notations.
I f (x) = O(g (x))
I ∃x0 , c : ∀x > x0 : f (x) < c × g (x)
I f is bounded above by g assymptotically
I f (x) = Ω(g (x))
I ∃x0 , c : ∀x > x0 : f (x) > c × g (x)
4/9
O and Ω
Now we can introduce two related notations.
I f (x) = O(g (x))
I ∃x0 , c : ∀x > x0 : f (x) < c × g (x)
I f is bounded above by g assymptotically
I f (x) = Ω(g (x))
I ∃x0 , c : ∀x > x0 : f (x) > c × g (x)
I f is bounded below by g assymptotically
4/9
O and Ω
Now we can introduce two related notations.
I f (x) = O(g (x))
I ∃x0 , c : ∀x > x0 : f (x) < c × g (x)
I f is bounded above by g assymptotically
I f (x) = Ω(g (x))
I ∃x0 , c : ∀x > x0 : f (x) > c × g (x)
I f is bounded below by g assymptotically
(
f (x) = O(g (x))
f (x) = Θ(g (x)) ⇔
f (x) = Ω(g (x))
4/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
I f1 (x) × f2 (x) = O(g1 (x) × g2 (x))
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
I f1 (x) × f2 (x) = O(g1 (x) × g2 (x))
I c × f1 (x) = O(g1 (x))
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
I f1 (x) × f2 (x) = O(g1 (x) × g2 (x))
I c × f1 (x) = O(g1 (x))
I f1 + c = O(g1 (x))
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
I f1 (x) × f2 (x) = O(g1 (x) × g2 (x))
I c × f1 (x) = O(g1 (x))
I f1 + c = O(g1 (x))
Examples
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
I f1 (x) × f2 (x) = O(g1 (x) × g2 (x))
I c × f1 (x) = O(g1 (x))
I f1 + c = O(g1 (x))
Examples
I log2 x = O(x)
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
I f1 (x) × f2 (x) = O(g1 (x) × g2 (x))
I c × f1 (x) = O(g1 (x))
I f1 + c = O(g1 (x))
Examples
I log2 x = O(x)
I 3 × x 2 − 5 × x + 7 = Θ(x 2 )
5/9
O properties
Let f1 (x) = O(g1 (x)) and f2 (x) = O(g2 (x)).
I f1 (x) + f2 (x) = O(max(g1 (x), g2 (x)))
I f1 (x) × f2 (x) = O(g1 (x) × g2 (x))
I c × f1 (x) = O(g1 (x))
I f1 + c = O(g1 (x))
Examples
I log2 x = O(x)
I 3 × x 2 − 5 × x + 7 = Θ(x 2 )
I x × (ln x + ln ln x) × ln ln x = O(x × ln x × ln ln x)
5/9
Asymptotical complexity
Consider a program
j = 1
for i = 1 to n
j = j × i
6/9
Asymptotical complexity
Consider a program
j = 1
for i = 1 to n
j = j × i
This cycle performs n iterations. Every iteration takes constant amount of operations.
6/9
Asymptotical complexity
Consider a program
j = 1
for i = 1 to n
j = j × i
This cycle performs n iterations. Every iteration takes constant amount of operations.
Asymptotical complexity of this program is O(n).
6/9
Asymptotical complexity
More complicated case
j = 1
for i = 1 to n
for j = 1 to i
print j
7/9
Asymptotical complexity
More complicated case
j = 1
for i = 1 to n
for j = 1 to i
print j
This cycle performs n×(n+1)
2 iterations. Every iteration takes constant amount of
operations.
7/9
Asymptotical complexity
More complicated case
j = 1
for i = 1 to n
for j = 1 to i
print j
This cycle performs n×(n+1)
2 iterations. Every iteration takes constant amount of
operations.
Asymptotical complexity of this program is O(n2 ). Constant doesn’t matter when we
are talking about asymptotical complexity.
7/9
Estimating run time from complexity
Consider you have a program which takes one number n as an input. Let’s try to
estimate its run time from its complexity and value of n.
8/9
Estimating run time from complexity
Consider you have a program which takes one number n as an input. Let’s try to
estimate its run time from its complexity and value of n.
complexity n = 10 n = 20 n = 100 n = 104 n = 105 n = 108
O(n!) ≈ 3 × 105 ≈ 2 × 1018 > 1020 > 1020 > 1020 > 1020
O(2n ) 1024 ≈ 106 > 1020 > 1020 > 1020 > 1020
O(n2 ) 100 400 104 108 1010 1016
O(n × log2 n) ≈ 30 ≈ 100 ≈ 700 ≈ 3 × 105 ≈ 2 × 106 ≈ 3 × 109
8/9
Estimating run time from complexity
Consider you have a program which takes one number n as an input. Let’s try to
estimate its run time from its complexity and value of n.
complexity n = 10 n = 20 n = 100 n = 104 n = 105 n = 108
O(n!) ≈ 3 × 105 ≈ 2 × 1018 > 1020 > 1020 > 1020 > 1020
O(2n ) 1024 ≈ 106 > 1020 > 1020 > 1020 > 1020
O(n2 ) 100 400 104 108 1010 1016
O(n × log2 n) ≈ 30 ≈ 100 ≈ 700 ≈ 3 × 105 ≈ 2 × 106 ≈ 3 × 109
You can suppose that average amount of operations per second CPU can perform is
≈ 3 × 108 . That is precise enough to check if yor program will pass Time Limit.
8/9
Estimating run time from complexity
Consider you have a program which takes one number n as an input. Let’s try to
estimate its run time from its complexity and value of n.
complexity n = 10 n = 20 n = 100 n = 104 n = 105 n = 108
O(n!) ≈ 3 × 105 ≈ 2 × 1018 > 1020 > 1020 > 1020 > 1020
O(2n ) 1024 ≈ 106 > 1020 > 1020 > 1020 > 1020
O(n2 ) 100 400 104 108 1010 1016
O(n × log2 n) ≈ 30 ≈ 100 ≈ 700 ≈ 3 × 105 ≈ 2 × 106 ≈ 3 × 109
You can suppose that average amount of operations per second CPU can perform is
≈ 3 × 108 . That is precise enough to check if yor program will pass Time Limit.
8/9
Estimating run time from complexity
Consider you have a program which takes one number n as an input. Let’s try to
estimate its run time from its complexity and value of n.
complexity n = 10 n = 20 n = 100 n = 104 n = 105 n = 108
O(n!) ≈ 3 × 105 ≈ 2 × 1018 > 1020 > 1020 > 1020 > 1020
O(2n ) 1024 ≈ 106 > 1020 > 1020 > 1020 > 1020
O(n2 ) 100 400 104 108 1010 1016
O(n × log2 n) ≈ 30 ≈ 100 ≈ 700 ≈ 3 × 105 ≈ 2 × 106 ≈ 3 × 109
You can suppose that average amount of operations per second CPU can perform is
≈ 3 × 108 . That is precise enough to check if yor program will pass Time Limit.
8/9
Thank you
for your attention!
9/9
