Computation complexity of
algorithm
Data Structures
and Algorithms
1
DSaA 2012/2013
Computation complexity of alg.
Computation complexity:
" worse-case complexity
" expected complexity
 aggregate analysis
 accounting method
2
DSaA 2012/2013
Notation
" An input I to an algorithm is the data, such
as numbers, character strings and
records, on which the operations of the
algorithm are performed
" Let Fn denote the set of all inputs of size n
tau
to an algorithm
" For I Îð Fn let Ä(I) denote the number of
basic operations performed when the
algorithm is executed with input I
3
DSaA 2012/2013
Worse-case complexity
The worse-case complexity of an algorithm
is the function W(n) such that W(n) equals
th maximum value of Ä(I), where I varies
over all inputs of size n. That is,
W(ðn)ð=ð max{ðtð(ðI)ðI ÎðFn}ð
4
DSaA 2012/2013
Worse-case complexity  exampl.
" Sorting n elements by generating all
permutation one by one, checking if the
next generated sequence is sorted. If it is
true, stop generating the permutations.
Assumption I: next generation is made in one elementary step
Assumption II: checking if the permutation is a solution is made in one elementary step
With assumption II: W(n) =ð 2n!
Without assumption II: W(n) =ð (1+ð n -ð1)×ðn! or W(n) =ð O(n!)
5
DSaA 2012/2013
Average (Expected) complexity
Let p(I) be a probability that I can be an input set
The average (expected) complexity of an
algorithm with finite input set Fn is defined as:
A(ðn)ð=ð
åðtð(ðI)ðp(ðI)ð=ð E[ðtð]ð
IÎðFn
6
DSaA 2012/2013
Formulation II
Let pi denote the probability that the
algorithm performs exactly i basic
operation; that is pi=P(Ä=i).
Then
W (n)
A(ðn)ð=ð E[ðtð]ð=ð
åðip
i
i=ð1
7
DSaA 2012/2013
Aggregate analysis
In aggregate analysis, we show that for all n, a sequence
of n operations takes worst-case time T(n) in total. In the
worst case, the average cost, or amortized cost, per
operation is therefore T(n)/n. Note that this amortized
cost applies to each operation, even when there are
several types of operations in the sequence.
8
DSaA 2012/2013
Aggregate analysis  bit counter
" We have a n-bits counter, which can
grows by one (n  size of input).
" Elementary operation  change of one bit
in a counter
0 0 0 0 0 0 0 0 0 126 0 1 1 1 1 1 1 0
1 1
1 0 0 0 0 0 0 0 1 127 0 1 1 1 1 1 1 1
2 8 (n)
2 0 0 0 0 0 0 1 0 128 1 0 0 0 0 0 0 0
1 1
3 0 0 0 0 0 0 1 1 129 1 0 0 0 0 0 0 1
9
DSaA 2012/2013
Bit counter  W(n), A(n)
" Worse-case complexity: W(n)=O(n)
" Average complexity ? Maybe A(n)=O(n/2)? No!
2n 2n 2n 2n
×ð1+ð ×ð2 +ð ×ð3+ðKð+ð ×ðn =ð1×ð2n-ð1 +ð 2×ð2n-ð2 +ð 3×ð2n-ð3 +ðKð+ð n×ð2n-ðn
2 4 8 2n
=ð (ð2n-ð1 +ð 2n-ð2 +ðKð+ð 20)ð+ð1×ð 2n-ð2 +ð 2×ð 2n-ð3 +ðKð(n -ð1)×ð20
=ð (ð2n -ð1)ð+ð(ð2n-ð2 +ðKð+ð 20)ð+ð1×ð 2n-ð3 +ðKð(n -ð 2)×ð 20
=ð (2n -ð1) +ð(ð2n-ð1 -ð1)ð+ðKð+ð (21 -ð1) +ð(ð20 -ð1)ð
=ð 2n+ð1 -ð1-ð n
2n+ð1
Þð
A(n) <ð =ð 2 A(n) =ð O(1)
2n
10
DSaA 2012/2013
The accounting method
In the accounting method of amortized analysis, we
assign differing charges to different operations, with
some operations charged more or less than they actually
cost. The amount we charge an operation is called its
amortized cost. When an operation's amortized cost
exceeds its actual cost, the difference is assigned to
specific objects in the data structure as credit. Credit can
be used later on to help pay for operations whose
amortized cost is less than their actual cost. Thus, one can
view the amortized cost of an operation as being split
between its actual cost and credit that is either deposited or
used up.
11
DSaA 2012/2013
Incrementing a binary counter
For the amortized analysis, let us charge an amortized cost of 2 dollars
to set a bit to 1. When a bit is set, we use 1 dollar (out of the 2 dollars
charged) to pay for the actual setting of the bit, and we place the other
dollar on the bit as credit to be used later when we flip the bit back to 0.
At any point in time, every 1 in the counter has a dollar of credit on it,
and thus we needn't charge anything to reset a bit to 0; we just pay for
the reset with the dollar bill on the bit.
0 0 0 0 0 0 0 0 0 126 0 1 1 1 1 1 1 0
1 1
1 0 0 0 0 0 0 0 1 127 0 1 1 1 1 1 1 1
2 8 (n)
2 0 0 0 0 0 0 1 0 128 1 0 0 0 0 0 0 0
1 1
3 0 0 0 0 0 0 1 1 129 1 0 0 0 0 0 0 1
Position with credit
12
DSaA 2012/2013