2013-2014-02 《Design and Analysis of Algorithm》
SCUN
2013-12-28
11
Worst-Case Analysis

In the worst case, we will either find the element on the last pass, or not find the element at all In each pass, only need 1 comparison. Hence, if we knew how many passes it has done, worst case is trivial If n = 2k-1, then there must be k = log(n+1) passes So, informally, we get: Tworst(n) = O(logn) If n is an arbitrary positive integer n, since after one pass, the algorithm faces the same situation but for an array half the size, we get the following recurrence relation for Tworst(n): Tworst(n) = Tworst ( n/2 ) + 1 n>1 Tworst(1) = 1 So, formally: Tworst(n) = logn + 1 = log(n+1) = O(logn)

Combinatorial problem
• • Fake-coin problem (S5.5) Josephus problem (S5.5)
Binary Search (basic idea)

Used with a sorted list (the list is in increasing order)
2013-2014-02 《Design and Analysis of Algorithm》 SCUN
2013-12-28 13
Average-Case Analysis (cont.)
• So we can represent binary search as a binary tree:
2013-2014-02 《Design and Analysis of Algorithm》
l 0; r n-1 while l r do m (l+r)/2 if K = A[m] return m else if K < A[m] r m-1 else l m+1 return -1
Hale Waihona Puke Thinking: How to rewrite this algorithm in recursive format?
Problem of size n
subproblem of size n/2
solution to the subproblem solution to the original problem
2013-2014-02 《Design and Analysis of Algorithm》
SCUN
2013-12-28

a a = n -1 a a
n =1
n >1
a n =1 n2 2 Decrease by constant n a = (a ) n > 1 and is even factor: ( n - 1) 2 2 ´ ) a n> 1 and is odd ( a
2013-2014-02 《Design and Analysis of Algorithm》 SCUN

2013-2014-02 《Design and Analysis of Algorithm》 SCUN
2013-12-28 8
Binary search example：Find the key value 14
0 1 2 3 4 5 6 7 8 9 10 11 12
3 14 27 31 39 42 55 70 74 81 85 93 98
2013-12-28 6
The Application of Decrease by a constant factor technique

Search problem • The binary search (S4.3, P135-139)

Numerical problem
• Russian peasant multiplication (S5.5)

Decrease by a constant factor (usually by half)
• • • • Binary search Fake-coin problem Russian peasant multiplication Josephus problem

Variable-size decrease
Goals of the Lecture

At the end of this lecture, you should
• Master the basic idea and all kinds of variations of decrease and conquer technique • Master the binary search algorithm and its best-case, worstcase and average-case analysis • Understand the fake coin problem and its solution • Be familiar with the Russian peasant multiplication method • Understand the josephus problem and its solution
2013-2014-02 《Design and Analysis of Algorithm》 SCUN
2013-12-28 12


Average-Case Analysis

Successful Search • If the search is always successful, there are n places (number of possible keys) the key could be found • We will consider each of these to be equivalent and so will give each a probability of 1/n • There is one place we check on the first pass, two places we could check on the second pass, and four places we could check on the third pass, and so on.
2013-2014-02 《Design and Analysis of Algorithm》
SCUN
2013-12-28
3
Decrease-and-Conquer (basic idea)
1.
2. 3.
Reduce problem instance to smaller instance of the same problem Solve smaller instance Extend solution of smaller instance to obtain solution to original instance
2013-2014-02 《Design and Analysis of Algorithm》
SCUN
2013-12-28
10
Best-case Analysis
The input instances in which the target matches the middle element will lead to the best case. This means only one comparison is done. So we get: Tbest (n) = Ω(1)
4
3 Types of Decrease and Conquer

Decrease by a constant (usually by 1)
• Insertion sort • Graph traversal algorithms (DFS and BFS) • Algorithms for generating permutations, subsets
n Brute Force: a n = a a a
Consider the problem of exponentiation: an
a a = n 2 n 2 a a
n

Divide and conquer:
Decrease by one:
n
n =1 n >1
Chapter 5
Decrease and Conquer (I)
Introduction to Decrease-and-Conquer Decrease-by-a-Constant-Factor Algorithms The Binary Search Fake-coin Problem Russian Peasant Multiplication Josephus Problem
low=0
27>14