Which of your algorithms is the best?
Execution of an algorithm often depends on
We could compare…
Räcke (2021)
Let’s start looking at memory requirements.
Although this might be less intuitive.
How much memory capacity is required for a computation?
Capacity is less important than execution time:
Why do we care about capacity nontheless?
So, the more relevant dimension for comparing algorithms is execution time.
Why consider time?
How can we measure time?
We need two things to measure time:
A machine model which defines durations of basic operations.
Actual durations. We get the number of operations a program needs via
Let’s measure some times (Tantau 2016)
Times \(t_1 ... t_6\) for
length \(( t_3
)\),i++ \(( t_4
)\),charAt \(( t_5
)\),return \(( t_6
)\).\(T( \text{ABCD05} ) = t_1 + 10t_2 + 5t_3 + 4t_4 + 5t_5 + t_6\)
Times \(t_1 ... t_6\) for
length \(( t_3
)\),i++ \(( t_4
)\),charAt \(( t_5
)\),return \(( t_6
)\).\(T( \text{ABCDEF} ) = t_1 + 13t_2 + 7t_3 + 6t_4 + 6t_5 + t_6\)
Times \(t_1 ... t_6\) for
length \(( t_3
)\),i++ \(( t_4
)\),charAt \(( t_5
)\),return \(( t_6
)\).\(T( 6 ) = t_1 + 13t_2 + 7t_3 + 6t_4 + 6t_5 + t_6\)
Times \(t_1 ... t_6\) for
length \(( t_3
)\),i++ \(( t_4
)\),charAt \(( t_5
)\),return \(( t_6
)\).\(T( l ) = t_1 + (2l+1)t_2 + (l+1)t_3 + lt_4 + lt_5 + t_6\)
Times \(t_1 ... t_6\) for
length \(( t_3
)\),i++ \(( t_4
)\),charAt \(( t_5
)\),return \(( t_6
)\).Execution time of the simple example:
\(T( l ) = t_1 + (2l+1)t_2 + (l+1)t_3 + lt_4 + lt_5
+ t_6\)
Actual time depends on a specific hardware.
But,
precise time measurements rather irrelevant.
We want a picture of the general behaviour of the algorithm.
We would like to compare complexity of problems.
Complexity classes are sets of related computational problems.
They define bounds for resources of algorithms tailored to a specific machine model
Complexity classes are often expressed using the Big O Notation.
Big O notation is a mathematical notation.
It describes the behavior of a function which is given huge inputs.
In computer science, big O notation is used to classify algorithms.
It describes how their run time or space requirements grow
as the
input size grows.
Different algorithms with the same asymptotic growth rate may be represented using the same O notation.
Big O notation is usually used to describe an upper bound on the complexity of an algorithm.
Central Ideas of O notation:
Definition of O notation:
Let \(g : \mathbb{N} \to \mathbb{N}\) be a function.
Then, the O-class or order of the function \(O(g)\)
yields the set of all functions
\(f : \mathbb{N} \to \mathbb{N}\)
\(O(g)\) is the set of functions that asymptotically grow not faster than \(g\).
Räcke (2021)
\(c \cdot g(n)\) has to
be in highlighted
area
Tantau (2016)
Example:
Let \(g(n) = n^2\) and \(f(n) = 3+17n^2\). Then, \(f \in O(g)\).
(With \(c=1000\) and \(n_0=1000\) this holds: \(3+17n^2 \le cn^2\) )
Example:
Let \(g(n) = n^2\) and \(f(n) = 1000\sqrt{n}\). Then, \(f \in O(g)\).
(With \(c=1000\) and \(n_0=0\) this holds: \(1000\sqrt{n} \le cn^2\) )
Example:
Let \(g(n) = n\) and \(f(n) = n^2\). Then, \(f \notin O(g)\).
We often write
Räcke (2021)
Räcke (2021)
Räcke (2021)
Räcke (2021)
Räcke (2021)
Räcke (2021)
Räcke (2021)
\(\begin{aligned} O(1) &\subsetneq O(\log n) \\ &\subsetneq O(\sqrt{n}) \\ &\subsetneq O(n) \\ &\subsetneq O(n \log n) \\ &\subsetneq O(n^2) \\ &\subsetneq O(n^3) \\ &\subsetneq O(2^n) \\ &\subsetneq O(n!) \end{aligned}\)
Up to \(O(n^3)\) is “acceptable”…
Benefits of O notation
Why talking about complexity again?
In the end, we want to utilize theory
to find new algorithmic
approaches.
More on that later.
mirco.schoenfeld@uni-bayreuth.de
Acknowledgement:
This script is inspired by Tantau (2016) and Räcke (2021).