PowerPoint Presentation
Algorithm Design & Analysis: Efficiency & Complexity
Slide #2 of 39
Overview
Algorithm Design & Analysis
Motivation
Efficiency and Space complexity
Efficiency: Time complexity
Of algorithms
Of problems
Conclusions and lessons
Slide #3 of 39
Motivation
We want to build computer systems that work
• And that work well!
To do this we need to think about several factors:
• They must give the correct answer
• Is this ALWAYS true?
• They must be reliable, maintainable, quick to
produce, cheap …
• Again, is this always true?
• They must be usable – by the user of the system
• They must be efficient
Slide #4 of 39
Efficient?
We want our software to:
• Run as quickly as possible
• Respond as quickly as possible
• Use as little memory as possible
• Use as little network bandwidth as possible
• Use as little power as possible
• …….
Slide #5 of 39
Efficient?
So, we are actually trying to optimise many things:
• The balance will depend on our problem
One serious issue we need to consider is:
• Our solution may work very well for ‘small’ problems
• But, if the problem gets more complex how does its
performance change?
• Does it get worse?
• Does it get MUCH worse?
• Does it get MUCH, MUCH worse?
Slide #6 of 39
What are we interested in?
Actually, there are several things to consider:
• Is our implementation of our algorithm or data
representation efficient:
• Could we improve our code to make it run faster?
• This might speed things up a bit
• or a lot … maybe 10 or 100 times
• Could we improve our data representation so it uses less
memory?
• Again we might improve things dramatically
• But what if our algorithm is inherently going to perform worse as
the amount of data increases?
• What if our problem is inherently hard and gets much harder as
the size of the problem grows?
Slide #7 of 39
So?
We need to understand how our problem and/or
algorithm changes in complexity as it gets larger.
Usually, we focus more on time complexity – how much
computation is involved in solving a problem:
• For instance, if we double the size of our problem
(e.g. twice as much data) then what happens to the
computation time:
• Does it stay the same?
• Does it get a bit harder? Maybe +30%
• Does it get a lot harder? Maybe +100%
• Does it get even worse? Maybe +400% or +800% or worse?
• Usually, we are interested in an almost qualitative measure
Slide #8 of 39
Space complexity
Usually, space (or bandwidth) complexity is not
considered in the same way as computational
complexity:
• Memory and bandwidth are limited by practical constraints
• We can add memory (and bandwidth or processing) to cope with
a bigger problem
• We can constrain our problem to the practical constraints
• We restrict the resolution of videos to what is practical
• We restrict the resolution of 3D models to what is practical
• We can use other techniques to reduce the memory
demands (e.g. compression or streaming)
Slide #9 of 39
An Example: video
Typical HD video:
• 1920×1080 pixels (4 bytes per pixel):
• ~2MPixels, ~8Mbytes
• 25 frames per second
• 200 Mbytes/sec
Solution:
• Compression (up to 200:1)
• Using empirical knowledge of human vision & video streams
• Lossy compression (cf. lossless compression)
• Reduce frame rate or resolution
• Constrained by practical constraints
Slide #10 of 39
How does the problem change with resolution?
If we double the resolution of a 2D image
• We x4 the number of pixels – n2
• If we have a 3D image (e.g. from an MRI scanner)
• If we double the resolution then: x8 – n3
The same problem will occur with 2D models and will be even
worse as the number of dimensions increases:
• n2, n3 ….
Slide #11 of 39
Time complexity
To develop a basic understanding
of algorithm design and efficiency in terms of
worst case time complexity.
Slide #12 of 39
Outline / Topics
Algorithm Design and Analysis
Efficiency
Time Complexity
Big-O Notation
Examples
Lessons
Slide #13 of 39
What is an Algorithm?
In mathematics, computer science, and related
subjects, an algorithm is an effective method
for solving a problem expressed as a finite
sequence of instructions.
o Muhammad bin -Khwarizmi
o a Muslim mathematician
o invented algorithms to solve quadratic equations
o the word algorithm derived from his Latin name
Algorithmi
o An even earlier algorithm is the sieve of Eratosthenes
Slide #14 of 39
Algorithm: question?
Which one is an algorithm?
A recipe for making tomato soup?
A procedure to sort 1000 numbers into ascending
numeric order?
A procedure to recognize a particular face in a crowd?
A method to order objects according to beauty?
Slide #15 of 39
Algorithm Design and Analysis
Multiple algorithms often exist for the same task:
All of them give correct results
How do we select the best one?
Many possible (and often conflicting) criteria:
Efficiency
?
simplicity, clarity
elegance, proofs of correctness
We need to ask
is my algorithm correct?
does my algorithm always terminate?
does an algorithm even exist?
Slide #16 of 39
Algorithm Efficiency
Resource usage of an algorithm
typically: time (runtime) and space (computer memory)
also: network usage, hardware requirements, …
…… consider trade-offs between resources
How do we measure the run-time of an algorithm?
benchmarking on representative set of inputs: empirical
analysis
analyse the (time) complexity
Slide #17 of 39
Algorithm Efficiency – Empirical Analysis
Idea: Implement the algorithm (a program) and time it
Question: How can we time a program?
Manual: Using stopwatch
Automatic: Using some timer function
Run the program for various input sizes and measure run time.
Slide #18 of 39
Algorithm Efficiency – Time Complexity
Time complexity:
the number of operations that an algorithm requires to execute,
in terms of the size of the input or problem
Note:
algorithm, not implementation
so: pseudocode; no fixed programming language, computer
architecture ……
“in terms of” – complexity defined as a function T(n)
Questions:
what do we mean by operations?
what do we mean by size?
we usually focus on worst-case, not average-case, analysis
Slide #19 of 39
Example # 1
Look up a value v in an array x of integers
Algorithm: Linear Search
inputs: array x of size n, integer v
return: index of first occurrence of v in x, or -1 if none
T(n) = n
Slide #20 of 39
Example # 2
Matrix-Vector Multiplication: x = A b
n x n matrix A, vector of b size n
Algorithm
inputs: matrix A, vector b
result stored in vector x (initially all 0)
T(n) = 2n2
Slide #21 of 39
Quadratic Growth
Consider the two functions
f(n) = n2
g(n) = n2 – 3n + 2
Around n = 3, they look very different
Slide #22 of 39
Quadratic Growth
Around n = 10, they look similar
Slide #23 of 39
Quadratic Growth
Around n = 100, they are almost the same
Slide #24 of 39
Quadratic Growth
Around n = 1000, the difference is indistinguishable!
Slide #25 of 39
Quadratic Growth
The absolute difference is large, such that,
f(1000) = 1000000
g(1000) = 997002
but the relative difference is very small,
and this difference goes to zero as n → ∞
Slide #26 of 39
Big-O Notation
Usually we don’t need exact complexity T(n)
it suffices to know the complexity class
we ignore constant factors/overheads, lower orders
focus on performance for large n (“asymptotic”)
Big-O notation
for example: O(n2) “O of n squared” “on the order of n2”
Examples
T(n) = n⟹ complexity class = O(n)
T(n) = n+2⟹ complexity class = O(n)
T(n) = 2n2 ⟹ complexity class = O(n2)
Slide #27 of 39
Big-O Notation
More Examples
T(n) = 10n3 + 1⟹ complexity class = O(n3)
T(n) = 5(n+2)⟹ complexity class = O(n)
T(n) = 1000⟹ complexity class = O(1)
T(n) = n2 + n + 1⟹ complexity class = O(n2)
Determining the complexity class
intuitively, it suffices to count the number of loops and the
number of times they are executed
Slide #28 of 39
Big-O Notation: Common Complexity Classes
Some common complexity classes:
O(1) = “Constant”
O(log
2
n) = “Logarithmic”
O(n) = “Linear”
O(n log
2
n) = “Log Linear”
O(n2) = “Quadratic”
O(n3) = “Cubic”
O(2n) = “Exponential”
Polynomial: O(n), O(n2), O(n3), … – “tractable”
Exponential: O(2n), O(Cn), – “intractable”
Slide #29 of 39
Some concrete numbers …
How many operations needed for an algorithm?
with complexity T(n) = f(n) and input size n
Slide #30 of 39
Some concrete numbers …
How much time needed for an algorithm?
assuming 1 million operations per second
Slide #31 of 39
Graphically
Slide #32 of 39
Example # 1 (again)
Look up a value v in an array x
Slide #33 of 39
Example # 1 (again)
Look up a value v in a sorted array x
Slide #34 of 39
Example # 1 (again)
Look up a value v in a sorted array x
Algorithm: Binary Search
inputs: sorted array x of size n,
integer v
return: index of first occurrence of
v in x, or -1 if none
Complexity = O(log
2
n)
Slide #35 of 39
Computing Complexity Classes
Determine total algorithm complexity
from the complexities of its components
1) Sequential algorithm phases
2) Function / Method calls
Slide #36 of 39
Sequential Algorithm Phases
Example: matrix-vector multiplication: x = A b
matrix-vector multiplication x = A b
initialise vector x (all 0), then add values to x
Complexity: O(n) + O(n2) = O(n2)
In general: “maximum” of complexities
Slide #37 of 39
Function/Method calls
Example: n array look-ups
Complexity: O(n) x O(log n) = O(n log n)
In general: “multiplication” of complexities
Slide #38 of 39
Computing Complexity Classes
Determine total algorithm complexity
from the complexities of its components
1) Sequential algorithm phases: “maximum”
e.g. O(n) + O(n2) = O(n2)
e.g. O(n) + O(log n) = O(n)
2) Function / Method calls: “multiplication”
e.g. O(n) x O(log n) = O(n log n)
e.g. O(n2) x O(1) = O(n2)
Slide #39 of 39
Question # 1
Given the following code fragment, what is its Big-O
running time?
a) O(n)
b) O(n2)
c) O(log n)
d) O(n3)
Slide #40 of 39
Question # 2
Given the following code fragment, what is its Big-O
running time?
a) O(n)
b) O(n2)
c) O(log n)
d) O(n3)
Slide #41 of 39
Question # 3
Given the following code fragment, what is its Big-O
running time?
a) O(n)
b) O(n2)
c) O(log n)
d) O(n3)
Slide #42 of 39
Some Harder Problems
Traveling Salesman Problem (TSP)
given n cities and the distances between them, what is
the shortest possible route that visits each city exactly
once and then returns to the first city?
https://en.wikipedia.org/wiki/Travelling_salesman_problem
https://en.wikipedia.org/wiki/Travelling_salesman_problem
Slide #43 of 39
Some Harder Problems
Boolean Satisfiability Problem (SAT)
Given a Boolean formula F(x
1
, x
2
, x
3
, …, x
n
)
Can F evaluate to 1 (true)?
If yes, return values of x
i
’s (satisfying the assignment) that
make F true.
In both cases (TSP & SAT):
lots of practical applications (Operations Research,
Optimization, Logistics, Model Checking, Software
Verification, … etc.)
also important problems in theoretical computer science
Slide #44 of 39
Algorithms vs. Problems
Algorithm complexity
worst-case run-time of algorithm – “efficiency”
actually an upper bound: algorithm A is in O(f(n)) if the
worst-case run-time is at most f(n)
usually use tightest (most informative) complexity
Problem complexity
complexity class = set of problems
problem X is in complexity class O(f(n)) if there exists an
algorithm to solve it in O(f(n)) – “difficulty”
again: this is an upper bound (and uses the tightest
possible)
sometimes consider lower bounds:
e.g. sorting: O(n log n)
Slide #45 of 39
P and NP
Complexity classes
O(1) ⊆ O(log n) ⊆ O(n) ⊆ O(n log n) ⊆ O(n2) ⊆ O(2n)
polynomial time (PTIME or P) – assumed to be “tractable”
Another famous class: NP
if we can “guess” a solution, it can be checked efficiently
(efficiently = in polynomial time)
NP-hard problems
e.g. travelling salesman problem, SAT, …
only exponential time algorithms are known
but some efficient heuristics exist in practice
P = NP?
Nobody knows …
US$1,000,000 prize if you solve it!
https://en.wikipedia.org/wiki/Millennium_Prize_Problems
Slide #46 of 39
Summary
Algorithm design and analysis:
Efficiency
Time Complexity
(worst-case) number of operations an algorithm needs to
execute, in terms of the size of the input or problem: T(n)
Big-O notation
complexity classes: O(n), O(n log n), O(2n), …
focus on large values of n (i.e. asymptotic behaviour)
ignore constants, lower factors
count loops/iterations, decompose algorithm
complexities for algorithms/problems
Slide #47 of 39
Summary & Lessons
Data Representation/Algorithms are tightly linked
Some algorithms are just better than others:
But sometimes the ‘best’ depends on the problem
Some problems are inherently hard (in the complexity
sense)
This doesn’t mean they cannot be solved
We may need to reformulate the problem
Constrain it
Relax conditions
E.g. instead of “find the best ….” we “find a very
good ….”