2IL50 Data Structures

2018-19 Q3

Lecture 2: Analysis of Algorithms

Analysis of algorithms

the formal way …

Analysis of algorithms
Can we say something about the running time of an algorithm without
implementing and testing it?

InsertionSort(A)
1. initialize: sort A[1]
2. for j = 2 to A.length
3. do key = A[j]
4. i = j-1
5. while i > 0 and A[i] > key
6. do A[i+1] = A[i]
7. i = i-1
8. A[i+1] = key
Analysis of algorithms
Analyze the running time as a function of n (# of input elements)
 best case
 average case
 worst case

An algorithm has worst case running time T(n) if for any input of
size n the maximal number of elementary operations executed is
T(n).

elementary operations
add, subtract, multiply, divide, load, store, copy, conditional and
unconditional branch, return …
Linear Search
Input: increasing sequence of n numbers A = ‹a1, a2, …, an› and value v
Output: an index i such that A[i] = v or NIL if v not in A

LinearSearch(A, v) v=7
1. for i = 1 to n
2. do if A[i] = v
3. then return i 1 3 4 7 8 14 17 21 28 35
4. return NIL

Running time
 best case: 1
 average case: n/2 (if successful)
 worst case: n
Binary Search
Input: increasing sequence of n numbers A = ‹a1, a2, …, an› and value v
Output: an index i such that A[i] = v or NIL if v not in A
BinarySearch(A, v)
1. x = 1
v=7
2. y = n + 1
3. while x + 1 < y
4. do h = ⌊(x + y)/2⌋ 1 3 4 7 8 14 17 21 28 35
5. do if A[h] ≤ v then x = h
6. else y = h
7. if A[x] = v then return x else return NIL

Running time
 best case: 1
 average case: log n
 worst case: log n
Analysis of algorithms: example
n=10 n=100 n=1000
InsertionSort: 15 n2 + 7n – 2 1568 150698 1.5 x 107
10466 204316 3.0 x 106
MergeSort: 300 n log n + 50 n

InsertionSort InsertionSort
6 x faster 1.35 x faster

The rate of growth of the running time as a MergeSort

function of the input is essential! 5 x faster

n = 1,000,000 InsertionSort 1.5 x 1013

MergeSort 6 x 109 2500 x faster !
Θ-notation
Let g(n) : N → N be a function. Then we have

Θ(g(n)) = { f(n) : there exist positive constants c1, c2, and n0 such
that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

“Θ(g(n)) is the set of functions that grow as fast as g(n)”

Θ-notation
Let g(n) : N → N be a function. Then we have

Θ(g(n)) = { f(n) : there exist positive constants c1, c2, and n0 such that
c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

c2g(n)

f(n)

c1g(n)

Notation: f(n) = Θ(g(n))

0
n0 n
Θ-notation
Let g(n) : N → N be a function. Then we have

Θ(g(n)) = { f(n) : there exist positive constants c1, c2, and n0 such
that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

Claim: 19n3 + 17n2 - 3n = Θ(n3)

Proof: Choose c1 = 19, c2 = 36 and n0 = 1.
Then we have for all n ≥ n0:
c1n3 = 19n3 (trivial)
≤ 19n3 + 17n2 - 3n (since 17n2 > 3n for n ≥ 1)
≤ 19n3 + 17n3 (since 17n2 ≤ 17n3 for n ≥1)
= c2n3 ■
Θ-notation
Let g(n) : N → N be a function. Then we have

Θ(g(n)) = { f(n) : there exist positive constants c1, c2, and n0 such
that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

Claim: 19n3 + 17n2 - 3n ≠ Θ(n2)

Proof: Assume that there are positive constants c1, c2, and n0 such that
for all n ≥ n0
c1n2 ≤ 19n3 + 17n2 - 3n ≤ c2n2
Since 19n3 + 17n2 - 3n ≤ c2n2 implies
19n3 ≤ c2n2 + 3n – 17n2 ≤ c2n2 (3n – 17n2 ≤ 0)
we would have for all n ≥ n0
19n ≤ c2.
O-notation
Let g(n) : N → N be a function. Then we have

O(g(n)) = { f(n) : there exist positive constants c and n0

such that f(n) ≤ cg(n) for all n ≥ n0 }

“O(g(n)) is the set of functions that grow

at most as fast as g(n)”
O-notation
Let g(n) : N → N be a function. Then we have

O(g(n)) = { f(n) : there exist positive constants c and n0

such that f(n) ≤ cg(n) for all n ≥ n0 }

cg(n)

f(n)

Notation: f(n) = O(g(n))

0
n0 n
Ω-notation
Let g(n) : N → N be a function. Then we have

Ω(g(n)) = { f(n) : there exist positive constants c and n0

such that cg(n) ≤ f(n) for all n ≥ n0 }

“Ω(g(n)) is the set of functions that grow

at least as fast as g(n)”
Ω-notation
Let g(n) : N → N be a function. Then we have

Ω(g(n)) = { f(n) : there exist positive constants c and n0

such that cg(n) ≤ f(n) for all n ≥ n0 }

f(n)

cg(n)

Notation: f(n) = Ω(g(n))

0
n0 n
Asymptotic notation

Θ(…) is an asymptotically tight bound “asymptotically equal”

O(…) is an asymptotic upper bound “asymptotically smaller or equal”

Ω(…) is an asymptotic lower bound “asymptotically greater or equal”

other asymptotic notation

o(…) → “grows strictly slower than”
ω(…) → “grows strictly faster than”
More notation …
f(n) = n3 + Θ(n2) means there is a function g(n) such that
f(n) = n3 + g(n) and g(n) = Θ(n2)

n
f(n) =  O(i) means there is one function g(i) such that
i 1 n
f(n) =  g(i) and g(i) = O(i)
i 1

O(1) or Θ(1) means a constant

2n2 + O(n) = Θ(n2) means for each function g(n) with g(n)=O(n)
we have 2n2 + g(n) = Θ(n2)
Quiz
1. O(1) + O(1) = O(1) true

2. O(1) + … + O(1) = O(1) false

n n
3.  O(i) = O(  i) true
i 1 i 1

4. O(n2) ⊆ O(n3) true

5. O(n3) ⊆ O(n2) false

6. Θ(n2) ⊆ O(n3) true

7. An algorithm with worst case running time false

O(n log n) is always slower than an algorithm
with worst case running time O(n) if n is
sufficiently large.
Quiz
8. n log2 n = Θ(n log n) false

9. n log2 n = Ω(n log n) true

10. n log2 n = O(n4/3) true

11. O(2n) ⊆ O(3n) true

12. O(2n) ⊆ Θ(3n) false

Analysis of algorithms
Analysis of InsertionSort
InsertionSort(A)
1. initialize: sort A[1]
2. for j = 2 to A.length
3. do key = A[j]
4. i = j-1
5. while i > 0 and A[i] > key
6. do A[i+1] = A[i]
7. i = i-1
8. A[i+1] = key

Get as tight a bound as possible on the worst case running time.

➨ lower and upper bound for worst case running time
Upper bound: Analyze worst case number of elementary operations
Lower bound: Give “bad” input example
Analysis of InsertionSort
InsertionSort(A)
1. initialize: sort A[1] O(1)
2. for j = 2 to A.length
3. do key = A[j]
O(1)
4. i = j-1
5. while i > 0 and A[i] > key
6. do A[i+1] = A[i] worst case:
7. i = i-1 (j-1) ∙ O(1)
8. A[i+1] = key O(1)

Upper bound: Let T(n) be the worst case running time of InsertionSort on an
array of length n. We have
n n
T(n) = O(1) +  { O(1) + (j-1)∙O(1) + O(1) } =  O(j) = O(n2)
j 2 j 2

Lower bound: Array sorted in decreasing order ➨ Ω(n2)

The worst case running time of InsertionSort is Θ(n2).
Analysis of MergeSort
MergeSort(A)
// divide-and-conquer algorithm that sorts array A[1..n]
1. if A.length = 1 O(1)
2. then skip
3. else
4. n = A.length ; n1 = floor(n/2); n2 = ceil(n/2); O(1)
5. copy A[1.. n1] to auxiliary array A1[1.. n1] O(n)
6. copy A[n1+1..n] to auxiliary array A2[1.. n2] O(n)
7. MergeSort(A1); MergeSort(A2) ??
8. Merge(A, A1, A2) O(n)

T(⌊n/2⌋) + T(⌈n/2⌉)

MergeSort is a recursive algorithm

➨ running time analysis leads to recursion
Analysis of MergeSort
Let T(n) be the worst case running time of MergeSort on an array of length n.
We have

O(1) if n = 1
T(n) =
T(⌊n/2⌋) + T(⌈n/2⌉) + Θ(n) if n > 1

frequently omitted since it

(nearly) always holds

often written as 2T(n/2)

Solving recurrences
Solving recurrences

Easiest: Master theorem

caveat: not always applicable

Alternatively: Guess the solution and use the substitution method to prove
that your guess is correct.

How to guess:
1. expand the recursion
2. draw a recursion tree
The master theorem
Let a and b be constants, let f(n) be a function, and let T(n)
be defined on the nonnegative integers by the recurrence
T(n) = aT(n/b) + f(n) can be rounded up or down
Then we have:
note: (logba) - ε
1. If f(n) = O(nlog a – ε) for some constant ε > 0, then T(n) = Θ(nlog a). b
b

2. If f(n) = Θ(nlog a), then T(n) = Θ(nlog a log n)

b b

3. If f(n) = Ω(nlog a + ε) for some constant ε > 0, and if af(n/b) ≤ cf(n) for
b
some constant c < 1 and all sufficiently large n,
then T(n) = Θ(f(n))
The master theorem: Example
T(n) = 4T(n/2) + n3

Master theorem with a = 4, b = 2, and f(n) = n3

logba = log24 = 2

➨ n3 = f(n) = Ω(nlog ab+ ε) = Ω(n2 + ε) with, for example, ε = 1

Case 3 of the master theorem gives T(n) = Θ(n3), if the regularity condition
holds.
choose c = ½ and n0 = 1

➨ af(n/b) = 4(n/2)3 = n3/2 ≤ cf(n) for n ≥ n0

➨ T(n) = Θ(n3)
The substitution method
The Master theorem does not always apply

In those cases, use the substitution method:

1. Guess the form of the solution.
2. Use induction to find the constants and show that the solution works

Use expansion or a recursion-tree to guess a good solution.

Recursion-trees
T(n) = 2T(n/2) + n

n/2 n/2

n/4 n/4 n/4 n/4

n/2i n/2i … n/2i

Θ(1) Θ(1) … Θ(1)

Recursion-trees
T(n) = 2T(n/2) + n

n n

n/2 n/2 2 ∙ (n/2) = n

n/4 n/4 n/4 n/4 4 ∙ (n/4) = n

log n

n/2i n/2i … n/2i 2i ∙ (n/2i) = n

Θ(1) Θ(1) … Θ(1) n ∙ Θ(1) = Θ(n) +

Θ(n log n)
Recursion-trees
T(n) = 2T(n/2) + n2

n2

(n/2)2 (n/2)2

(n/4)2 (n/4)2 (n/4)2 (n/4)2

(n/2i)2 (n/2i)2 … (n/2i)2

Θ(1) Θ(1) … Θ(1)

Recursion-trees
T(n) = 2T(n/2) + n2

n2 n2

(n/2)2 (n/2)2 2 ∙ (n/2)2 = n2/2

(n/4)2 (n/4)2 (n/4)2 (n/4)2 4 ∙ (n/4)2 = n2/4

(n/2i)2 (n/2i)2 … (n/2i)2 2i ∙ (n/2i) 2 = n2/2i

Θ(1) Θ(1) … Θ(1) n ∙ Θ(1) = Θ(n) +

Θ(n2)
Recursion-trees
T(n) = 4T(n/2) + n

n/2 n/2 n/2 n/2

… n/4 n/4 n/4 n/4 …

Θ(1) Θ(1) … Θ(1)

Recursion-trees
T(n) = 4T(n/2) + n

n n

n/2 n/2 n/2 n/2 4 ∙ (n/2) = 2n

… n/4 n/4 n/4 n/4 … 16 ∙ (n/4) = 4n

Θ(1) Θ(1) … Θ(1) n2 ∙ Θ(1) = Θ(n2) +

Θ(n2)
The substitution method
2 if n = 1
T(n) =
2T(⌊n/2⌋) + n if n > 1

Claim: T(n) = O(n log n)

Proof: by induction on n
to show: there are constants c and n0 such that
T(n) ≤ c n log n for all n ≥ n0
n = 1 ➨ T(1) = 2 ≤ c 1 log 1 ➨ n0 = 2

n = n0 = 2 is a base case
⌊3/2⌋ = 1, ⌊4/2⌋ = 2 ➨ 3 must also be
Need more base cases?
base case
Base cases:
n = 2: T(2) = 2T(1) + 2 = 2∙2 + 2 = 6 = c 2 log 2 for c = 3
n = 3: T(3) = 2T(1) + 3 = 2∙2 + 3 = 7 ≤ c 3 log 3
The substitution method
2 if n = 1
T(n) =
2T(⌊n/2⌋) + n if n > 1

Claim: T(n) = O(n log n)

Proof: by induction on n
to show: there are constants c and n0 such that
T(n) ≤ c n log n for all n ≥ n0
choose c = 3 and n0 = 2

Inductive step: n > 3

T(n) = 2T(⌊n/2⌋) + n
≤ 2 c n/2 log n/2 + n (ind. hyp.)
≤ c n ((log n) - 1) + n
≤ c n log n ■
The substitution method
Θ(1) if n = 1
T(n) =
2T(⌊n/2⌋) + n if n > 1

Claim: T(n) = O(n)

Proof: by induction on n
Base case: n = n0
T(2) = 2T(1) + 2 = 2c + 2 = O(2)
Inductive step: n > n0
T(n) = 2T(⌊n/2⌋) + n
= 2O(⌊n/2⌋) + n (ind. hyp.)
= O(n) ■
Never use O, Θ, or Ω in a proof by induction!
Tips
Analysis of recursive algorithms:
find the recursion and solve with master theorem if possible

Analysis of loops: summations

Some standard recurrences and sums:

 T(n) = 2T(n/2) + Θ(n) ➨ T(n) = Θ(n log n)

i 
i1
 ½ n(n+1) = Θ(n2)
n

i
i1
2


 ⅙ n(n+1)(2n+1) = Θ(n3)