Fundamental principles of
algorithms analysis
Data Structures
and Algorithms
DSaA 2012/2013
Algorithm definitions
" A step-by-step problem-solving procedure, especially an established,
recursive computational procedure for solving a problem in a finite number
of steps. (The American Heritage dictionaries)
" An algorithm is a set of precise (i.e., unambiguous) rules that specify how to
solve some problem or perform some task (LINFO).
" Properties of algorithms generally include: input/output (i.e., receives input
and generates output), precision (each step is precisely stated),
determinism (the intermediate results of each step of execution are unique
and are determined only by inputs and results of the previous step),
termination (ends after a finite number of instructions execute),
correctness (the output generated is correct) and generality (each
algorithm applies to a set of inputs). (LINFO)
" Informally, an algorithm is any well-defined computational procedure that
takes some value, or set of values, as input and produces some value, or
set of values, as output. An algorithm is thus a sequence of computational
steps that transform the input into the output (Cormen at al.)
DSaA 2012/2013
Algorithms
" Are in every computer program. But also in any
non-computer procedure:
 Instruction of tools
 Recipe (for food, for medicine)
 Technology
 Calculation in science
" Can be expressed as:
 Colloquial language
 Code in known programming language
 Pseudocode
 Diagrams
 Mix of above
DSaA 2012/2013
Assumptions
" Problems
 decidable , undecidable
 decision problems, computational (function) problems
" Algorithms
 correct: An algorithm is said to be correct if, for every input
instance, it halts with the correct output. We say that a correct
algorithm solves the given computational problem.
 incorrect: An incorrect algorithm might not halt at all on some
input instances, or it might halt with an answer other than the
desired one. Contrary to what one might expect, incorrect
algorithms can sometimes be useful, if their error rate can be
controlled
 finite runtime
DSaA 2012/2013
Fundamental notions
" elementary operation (step):
 algebraic operation (addition, substraction, & )
 comparison (<, <=,& )
 coping, assigment (a=b)
" size of problem (n)  number of input data:
 theory: number of bits
 real number: number of numbers to sort
 more useful number: size of matrix
 more than one number: for graph
" complexity of problem/algorithm is represented
as a function of n, i.e. f(n)
DSaA 2012/2013
The fact
" The simplest algorithm for solving a
problem is often not the most efficient.
Therefore, when designing an algorithm,
do not settle for just any algorithm that
work.
DSaA 2012/2013
Improving algorithm  an example
" How to calculate nk ? (k in R)
" Simple  from definition:
Power(n,k)
{
Result=1;
n0=1
while(k>0)
nk=n*n(k-1) for k>=1
{
Result=Result*n;
k--;
}
return Result;
}
k multiplications
DSaA 2012/2013
nk  better algorithm (1)
" n89=n(n44)2, n44=(n22)2, n22=(n11)2,
n11=n(n5)2, n5=n(n2)2, n2=n*n
Power(n,k)
{
if(k==0) return 1;
if(k==1) return n;
n2k=(nk)2
result=Power(n,k/2);
n2k+1=n(nk)2
if(k%2==0)
return result*result;
else
2*log(k) multiplications
return n*result*result;
}
Recursion !
DSaA 2012/2013
nk  better algorithm (2)
" n89=n64*n16*n8*n1=(((((n2)2)2)2)2)2)*(((n2)2)2)2
*((n2)2)2*n
Power(n,k)
6 4 3 0
{
n89 =ð n2 n2 n2 n2 =ð n1011001
Result=1;
pow=n;
while(k>0)
{
if((k%2)==1)
Result*=pow;
pow*=pow;
k/=2;
}
2*log(k) multiplications
return Result;
}
DSaA 2012/2013
Asymptotic Notation  Big Theta
For a given function g(n), we denote by Åš(g(n)) the set of
functions f(n) having the property that there exists positive
constants c1,c2, and n0 such that for all n>=n0,
c1g(n) d" f(n) d" c2g(n)
c2g(n)
f(n)
Åš determines
an equivalence
c1g(n)
relation
f(x) has order g(x)
n
n0
DSaA 2012/2013
Big Theta - example
" f(x)=x2+100x+1000
" f(x)= Åš (x2) , because:
 for n=1000,c1=1, c2=10 we have for x>=n:
" x2+100x+1000>x2
" x2+100x+1000<10x2
(1.000.000+100.000+1000<10*1.000.000)
DSaA 2012/2013
Asymptotic Notation  Big Oh
For a given function g(n), we denote by O(g(n)) the set of
functions f(n) having the property that there exists positive
constants c and n0 such that for all n>=n0
f(n) d" c"g(n)
cg(n)
We say that f has a
f(n)
smaller order than g
n
n0
DSaA 2012/2013
Big Oh - example
" f(x)=x |sin(x)|
" f(x)= O(x) , because:
 for n=1,c=1, we have for x>=n:
" |sin(x)|<=1
" x|sin(x)|<=x
" also: f(x)=O(x2)
DSaA 2012/2013
Asymptotic Notation  Big Omega
For a given function g(n), we denote by Wð(g(n)) the set of
functions f(n) having the property that there exists
positive constants c and n0 such that for all n>=n0,
c"g(n) d" f(n)
f(n)
We say that f has a
larger order than g
cg(n)
n
n0
DSaA 2012/2013
Dependences
Functions that have
O(n2)
a smaller order than
n2
nlogn
55 n
2n +ð 3
6n2 +ð n +ð nlogn
6n2 +ð 3
Qð(n2)
n2
2n
n4 +ð n3
n!+ð n
Functions that have
Wð(n2)
a larger order than
n2
DSaA 2012/2013
Complexity of problem/algorithm
" time complexity of a problem is the number of
steps that it takes to solve an instance of the
problem as a function of the size of the input,
using the most efficient algorithm
" space complexity of a problem is a related
concept, that measures the amount of space, or
memory required by the algorithm
" time complexity and space complexity can be
considered for a chosen algorithm.
DSaA 2012/2013
Hierarchy of orders  complexity classes
O(nn )
O(n!)
NP-complete problems
O(n2n )
NP problems
O(2n )
O(n3)
O(n2 )
O(nlogn)
O(n)
P problems
O( n)
O(logn)
O(1)
DSaA 2012/2013
Relationships
" transitivity
f (n) =ð Qð(g(n)) i g(n) =ð Qð(h(n)) implies f (n) =ð Qð(h(n))
f (n) =ð Oð(g(n)) i g(n) =ð Oð(h(n)) implies f (n) =ð Oð(h(n))
f (n) =ð Wð(g(n)) i g(n) =ð Wð(h(n)) implies f (n) =ð Wð(h(n))
" reflexivity
f (n) =ð Qð( f (n))
f (n) =ð Oð( f (n))
f (n) =ð Wð( f (n))
" symmetry
f (n) =ð Qð(g(n)) if and only if g(n) =ð Qð( f (n))
" transitive symmetry
f (n) =ð Oð(g(n)) if and only if g(n) =ð Wð( f (n))
DSaA 2012/2013
Relationships (cont.)
" Others property
nm = O(nk), where m d" k
O(f(n))+O(g(n)) = O(|f(n)|+|g(n)|)
c"O(f(n)) = O(f(n)), where c is constant
O(O(f(n)) = O(f(n))
O(f(n))"O(g(n)) = O(f(n)"g(n))
O(f(n)"g(n)) = f(n)"O(g(n))
DSaA 2012/2013
Problems classification
" P problems
 Computation complexity is at most
polynomial
" sorting
" matrix multiplication
NP
" shortest path
" NP problems
 Computation complexity is at least
P
exponential
" simplex method
" monk s puzzle problem
NP-complete
" NP-complete problems
" boolean satisfiability problem (SAT)
" Hamilton s cycle
" set division
DSaA 2012/2013
Complexity comparison
Complexity Size n
function
10 20 30 40 50 60
0,00000001s 0,00000002s 0,00000003s 0,00000004s 0,00000005s 0,00000006s
n
0,0000001s 0,0000004s 0,0000009s 0,0000016s 0,0000025s 0,0000036s
n2
n5 0,0001s 0,0032s 0,0243s 0,1024s 0,3125s 0,7776s
n10 10s 2,8h 6,8 days 121,4 3,1 years 19,2
days years
0,0000001s
2n 0,001s 1s 18,3 min 13 days 36,6
years
0,000006s
3n 3,5s 2,4 days 385 2*107 1,3*1012
years years years
n! 0,003s 77 years 8*1015 2*1032 9*1047 2*1065
years years years years
age of universe = 13,7*109 years
DSaA 2012/2013
Complexity comparison (cont.)
Complexity Size n
function
10 100 1000 10000 100000 1000000
0,00000001s 0,0000001s 0,000001s 0,00001s 0,0001s 0,001s
n
0,00000003s 0,0000006s
nlog2n 0,00001s 0,0001s 0,0016s 0,02s
0,0000001s
n2 0,00001s 0,001s 0,1s 10s 16,6min
0,000001s
n3 0,001s 1s 16,6min 11,5 days 31,7
years
DSaA 2012/2013
Complexity comparison (cont.)
Complexity Size of the biggest problem solved during 1h
function
By current computer By computer By computer
100 times faster 1000 times faster
n N1 100N1 1000N1
n2 N2 10N2 31,6N2
n3 N3 4,64N3 10N3
n5 N4 2,5N4 3,98N4
2n N5 N5+6,64 N5+9,97
3n N6 N6+4,19 N6+6,29
DSaA 2012/2013