COSC 2 Dis
Chapter 22:
Developing Efficient Algorithms
Dr. Adriana Badulescu
Objectives ▪ To estimate algorithm efficiency using the Big notation (§22.2).
▪ To explain growth rates and why constants and nondominating terms can be ignored in the estimation (§22.2).
▪ To determine the complexity of various types of algorithms (§22.3).
▪ To analyze the binary search algorithm (§22.4.1).
▪ To analyze the selection sort algorithm (§22.4.2).
▪ To analyze the insertion sort algorithm (§22.4.3).
▪ To analyze the Tower of Hanoi algorithm (§22.4.4).
▪ To describe common growth functions (constant, logarithmic, log-linear, quadratic, cubic, exponential) (§22.4.5).
▪ To design efficient algorithms for finding Fibonacci numbers using dynamic programming (§22.5).
▪ To find the GCD using Euclid’s algorithm (§22.6).
▪ To finding prime numbers using the sieve of Eratosthenes (§22.7).
▪ To design efficient algorithms for finding the closest pair of points using the divide-and-conquer approach (§22.8).
▪ To solve the Eight Queens problem using the backtracking approach (§22.9).
▪ To design efficient algorithms for finding a convex hull for a set of points (§22.10).
Executing Time ▪ Suppose two algorithms perform the same task such as search
(linear search vs. binary search). Which one is better? One possible approach to answer this question is to implement these algorithms in Java and run the programs to get execution time. But there are two problems for this approach:
▪ First, there are many tasks running concurrently on a computer. The execution time of a particular program is dependent on the system load.
▪ Second, the execution time is dependent on specific input. Consider linear search and binary search for example. If an element to be searched happens to be the first in the list, linear search will find the element quicker than binary search.
Growth Rate ▪ It is very difficult to compare algorithms by measuring
their execution time. ▪ To overcome these problems, a theoretical approach
was developed to analyze algorithms independent of computers and specific input.
▪ This approach approximates the effect of a change on the size of the input. In this way, you can see how fast an algorithm’s execution time increases as the input size increases, so you can compare two algorithms by examining their growth rates.
Big O Notation ▪ Consider linear search. The linear search algorithm compares
the key with the elements in the array sequentially until the key is found or the array is exhausted. If the key is not in the array, it requires n comparisons for an array of size n. If the key is in the array, it requires n/2 comparisons on average.
▪ The algorithm’s execution time is proportional to the size of the array. If you double the size of the array, you will expect the number of comparisons to double. The algorithm grows at a linear rate.
▪ The growth rate has an order of magnitude of n. Computer scientists use the Big O notation to abbreviate for “order of magnitude.” Using this notation, the complexity of the linear search algorithm is O(n), pronounced as “order of n.”
Best, Worst, and Average Cases ▪ For the same input size, an algorithm’s execution time may vary,
depending on the input. ▪ An input that results in the shortest execution time is called the
best-case input and an input that results in the longest execution time is called the worst-case input.
▪ Best-case and worst-case are not representative, but worst-case analysis is very useful. You can show that the algorithm will never be slower than the worst-case.
▪ An average-case analysis attempts to determine the average amount of time among all possible input of the same size. Average- case analysis is ideal, but difficult to perform, because it is hard to determine the relative probabilities and distributions of various input instances for many problems. Worst-case analysis is easier to obtain and is thus common. So, the analysis is generally conducted for the worst-case.
Ignoring Multiplicative Constants ▪ The linear search algorithm requires n comparisons in the worst-
case and n/2 comparisons in the average-case. Using the Big O notation, both cases require O(n) time. The multiplicative constant (1/2) can be omitted. Algorithm analysis is focused on growth rate. The multiplicative constants have no impact on growth rates. The growth rate for n/2 or 100n is the same as n, i.e., O(n) = O(n/2) = O(100n).
f(n)
n
100
200
n n/2 100n
100
200
50
100
10000
20000
2 2 2 f(200) / f(100)
Ignoring Non-Dominating Terms ▪ Consider the algorithm for finding the maximum number in an
array of n elements. ▪ If n is 2, it takes one comparison to find the maximum number. ▪ If n is 3, it takes two comparisons to find the maximum number. ▪ In general, it takes n-1 times of comparisons to find maximum
number in a list of n elements. ▪ Algorithm analysis is for large input size. If the input size is small,
there is no significance to estimate an algorithm’s efficiency. As n grows larger, the n part in the expression n-1 dominates the complexity.
▪ The Big O notation allows you to ignore the non-dominating part (e.g., -1 in the expression n-1) and highlight the important part (e.g., n in the expression n-1).
▪ So, the complexity of this algorithm is O(n).
Useful Mathematic Summations
▪ Useful formulas for computing the program complexity
12
12 22....2222
1
1 ....
2
)1( )1(....321
1 )1(3210
1 )1(3210
−
− =++++++
−
− =++++++
+ =+−++++
+ −
+ −
n nn
n nn
a
a aaaaaa
nn nn
Examples: Determining Big-O ▪ Repetition
▪ Sequence
▪ Selection
▪ Logarithm
Repetition: Simple Loops
Repetition: Nested Loops
Repetition: Nested Loops
Repetition: Nested Loops
Sequence
Selection
Constant Time ▪ The Big O notation estimates the execution time of an algorithm in
relation to the input size. ▪ If the time is not related to the input size, the algorithm is said to
take constant time with the notation O(1). ▪ For example, a method that retrieves an element at a given index
in an array takes constant time, because it does not grow as the size of the array increases.
Binary Search
Logarithm: Analyzing Binary Search ▪ The binary search algorithm, searches a key in a sorted array.
▪ Each iteration in the algorithm contains a fixed number of
operations, denoted by c.
▪ Let T(n) denote the time complexity for a binary search on a list of
n elements. Without loss of generality, assume n is a power of 2
and k=logn.
▪ Since binary search eliminates half of the input after two
comparisons, 𝑇(𝑛) = 𝑇(
𝑛
2 ) +⥂ 𝑐 = 𝑇(
𝑛
22 ) + 𝑐 + 𝑐 =. . .= 𝑇(
𝑛
2𝑘 ) +⥂ 𝑐𝑘 = 𝑇(1) + 𝑐 ⥂ log𝑛
= 1 + 𝑐 log𝑛 = 𝑂(log𝑛)
Logarithmic Time ▪ Ignoring constants and smaller terms, the complexity of the
binary search algorithm is O(logn).
▪ An algorithm with the O(logn) time complexity is called a
logarithmic algorithm.
▪ The base of the log is 2, but the base does not affect a
logarithmic growth rate, so it can be omitted.
▪ The logarithmic algorithm grows slowly as the problem size
increases.
▪ If you square the input size, you only double the time for the
algorithm.
Selection Sort
Analyzing Selection Sort ▪ The selection sort algorithm finds the smallest number in the list
and places it first. It then finds the smallest number remaining and places it second, and so on until the list contains only a single number.
▪ The number of comparisons is n-1 for the first iteration, n-2 for the second iteration, and so on. Let T(n) denote the complexity for selection sort and c denote the total number of other operations such as assignments and additional comparisons in each iteration. So,
▪ Ignoring constants and smaller terms, the complexity of the selection sort algorithm is O(n2).
𝑇(𝑛) = (𝑛 − 1) + 𝑐 + (𝑛 − 2) + 𝑐. . .+2 + 𝑐 + 1 + 𝑐 = 𝑛2
2 − 𝑛
2 + 𝑐𝑛
Quadratic Time ▪ An algorithm with the O(n2) time complexity is called a
quadratic algorithm.
▪ The quadratic algorithm grows quickly as the problem
size increases.
▪ If you double the input size, the time for the algorithm is
quadrupled.
▪ Algorithms with a nested loop are often quadratic.
Tower Of Hanoi
Analyzing Tower of Hanoi ▪ The Tower of Hanoi problem presented in Listing 18.7,
TowerOfHanoi.java, moves n disks from tower A to tower B with
the assistance of tower C recursively as follows:
▪ Move the first n – 1 disks from A to C with the assistance of
tower B.
▪ Move disk n from A to B.
▪ Move n - 1 disks from C to B with the assistance of tower A.
▪ Let T(n) denote the complexity for the algorithm that moves disks
and c denote the constant time to move one disk, i.e., T(1) is c. So,
)2()12(2...22
2...2)1(2)))2((2(2
)1(2)1()1()(
21
21
nnnn
nn
Occccc
cccTccnT
cnTnTcnTnT
=−=++++=
=++++=++−=
+−=−++−=
−−
−−
Common Recurrence Relations Recurrence Relation Result Example
)1()2/()( OnTnT += )(log)( nOnT = Binary search, Euclid’s GCD
)1()1()( OnTnT +−= )()( nOnT = Linear search
)1()2/(2)( OnTnT += )()( nOnT =
)()2/(2)( nOnTnT += )log()( nnOnT = Merge sort (Chapter 24)
)log()2/(2)( nnOnTnT += )log()( 2
nnOnT =
)()1()( nOnTnT +−= )()( 2
nOnT = Selection sort, insertion sort
)1()1(2)( OnTnT +−= )2()( n
OnT = Towers of Hanoi
)1()2()1()( OnTnTnT +−+−= )2()( n
OnT = Recursive Fibonacci algorithm
Comparing Common Growth Functions
Comparing Common Growth Functions )2()()()log()()(log)1(
32 n OnOnOnnOnOnOO
O(1)
O(logn)
O(n)
O(nlogn)
O(n 2 )
O(2 n )
Case Study: Fibonacci Numbers
Finonacci series: 0 1 1 2 3 5 8 13 21 34 55 89…
indices: 0 1 2 3 4 5 6 7 8 9 10 11
fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index -1) + fib(index -2); index >=2
Complexity for Recursive Fibonacci Numbers
Since and
Therefore, the recursive Fibonacci method takes 𝑂(2𝑛)
)2(
)12...2(2
)12()1(2
)12...2()1(2
2...2)1(2
...
2)2(2
))2(2(2
)1(2
)2()1()(
21
11
21
21
2
n
nn
nn
nn
nn
O
cc
cT
cT
cccT
ccnT
ccnT
cnT
cnTnTnT
=
++++=
−+=
++++=
++++
++−=
++−
+−
+−+−=
−−
−−
−−
−−
)2(
222...22
222...2)1(2
222)222(2
22)22(2
2)2)4(2(2
2)2(2
)2()3()2(
)2()1()(
232/2/
232/2/
233
22
n
nn
nn
O
ccccc
ccccT
cccnT
ccnT
ccnT
cnT
cnTcnTnT
cnTnTnT
=
+++++=
+++++
+++−−−
++−−
++−
+−
+−++−+−=
+−+−=
Case Study: Non-recursive Fibonacci
Obviously, the complexity of this new algorithm is 𝑂(n) This is a tremendous improvement over the recursive algorithm.
Fibonacci
Dynamic Programming ▪ The algorithm for computing Fibonacci numbers presented
here uses an approach known as dynamic programming.
▪ Dynamic programming is to solve subproblems, then combine the solutions of subproblems to obtain an overall solution.
▪ This naturally leads to a recursive solution. However, it would be inefficient to use recursion, because the subproblems overlap.
▪ The key idea behind dynamic programming is to solve each subprogram only once and storing the results for subproblems for later use to avoid redundant computing of the subproblems.
Case Study: GCD Algorithms
▪ The greatest common divisor )(GCD) of two integers is the largest number that divides both integers.
▪ Brute Force Algorithms are straightforward methods of solving a problem that rely on sheer computing power and trying every possibility rather than advanced techniques to improve efficiency.
Case Study: GCD Algorithms Version 1
Obviously, the complexity of this algorithm is 𝑂(n)
Case Study: GCD Algorithms Version 2
The worst-case time complexity of this algorithm is still 𝑂(n)
Case Study: GCD Algorithms Version 3
The worst-case time complexity of this algorithm is still 𝑂(n)
Euclid’s GDC algorithm Let gcd(m, n) denote the gcd for integers m and n:
▪If m % n is 0, gcd (m, n) is n.
▪Otherwise, gcd(m, n) is gcd(n, m % n).
m = n*k + r
if p is divisible by both m and n, it must be divisible by r
m / p = n*k/p + r/p
Euclid’s Algorithm Implementation
The time complexity of this algorithm is O(logn). See the textbook for the proof.
Finding Prime Numbers
▪ An integer greater than 2 is prime if its only positive divisor is 1 or itself
▪ Compare three versions:
▪ Brute-force
▪ Check possible divisors up to Math.sqrt(n)
▪ Check possible prime divisors up to Math.sqrt(n)
Finding Prime Numbers Compare three versions:
▪Brute-force
▪Check possible divisors up to Math.sqrt(n)
▪Check possible prime divisors up to Math.sqrt(n)
Finding Prime Numbers ▪Brute-force version
▪ Checks all numbers between 2 and n-1
Finding Prime Numbers
▪Check possible divisors up to Math.sqrt(n)
Finding Prime Numbers ▪Check possible prime divisors up to
Math.sqrt(n)
Divide-and-Conquer ▪ The divide-and-conquer approach divides the
problem into subproblems, solves the subproblems, then combines the solutions of subproblems to obtain the solution for the entire problem.
▪ Unlike the dynamic programming approach, the subproblems in the divide-and-conquer approach don’t overlap.
▪ A subproblem is like the original problem with a smaller size, so you can apply recursion to solve the problem. In fact, all the recursive problems follow the divide-and-conquer approach.
Case Study: Closest Pair of Points
)log()()2/(2)( nnOnOnTnT =+=
http://www.cs.armstrong.edu/liang/animation/web/ ClosestPair.html
Eight Queens
0 4
7
5
2
6
1
3
queens[0] queens[1]
queens[2]
queens[3]
queens[4]
queens[5]
queens[6]
queens[7]
Eight Queens There are many possible candidates? How do you find a solution? The backtracking approach is to search for a candidate incrementally and abandons it as soon as it determines that the candidate cannot possibly be a valid solution, and explores a new candidate.
Convex Hull Given a set of points, a convex hull is a smallest convex polygon that encloses all these points, as shown in Figure a. A polygon is convex if every line connecting two vertices is inside the polygon. For example, the vertices v0, v1, v2, v3, v4, and v5 in Figure a form a convex polygon, but not in Figure b, because the line that connects v3 and v1 is not inside the polygon.
v4
v3
v2
v1
v0 v5
v4
v3
v2
v1
v0 v5
Figure a Figure b
Gift-Wrapping Step 1: Given a set of points S, let the points in S be labeled s0, s1, ..., sk. Select the rightmost lowest point h0 in the set S. Let t0 be h0.
h0
t0
s
t1
(Step 2: Find the rightmost point t1): Let t1 be s0.
For every point p in S, if p is on the right side of
the direct line from t0 to t1, then let t1 be p.
t0
t1
t1 = h0 t0
Step 3: If t1 is h0, done.
Step 4: Let t0 be t1, go to Step 2.
Gift-Wrapping Algorithm Time ▪ Finding the rightmost lowest point in Step 1 can
be done in O(n) time. Whether a point is on the left side of a line, right side, or on the line can decided in O(1) time (see Exercise 3.32). Thus, it takes O(n) time to find a new point t1 in Step 2. Step 2 is repeated h times, where h is the size of the convex hull. Therefore, the algorithm takes O(hn) time. In the worst case, h is n.
Graham’s Algorithm Given a set of points S, select the rightmost lowest point and name it p0 in the set S. As shown in Figure 22.10a, p0 is such a point.
Sort the points in S angularly along the x-axis with p0 as the center. If there is a tie and two points have the same angle, discard the one that is closest to p0. The points in S are now sorted as p0, p1, p2, ..., pn-1.
p0
p0 x-axis
p2
p1
The convex hull is discovered incrementally. Initially, p0, p1, and p2 form a convex hull. Consider p3. p3 is outside of the current convex hull since points are sorted in increasing order of their angles. If p3 is strictly on the left side of the line from p1 to p2, push p3 into H. Now p0, p1, p2, and p3 form a convex hull. If p3 is on the right side of the line from p1 to p2 (see Figure 22.10d), pop p2 out of H and push p3 into H. Now p0, p1, and p3 form a convex hull and p2 is inside of this convex hull.
p0 x-axis
p2
p1
p3
X
p0 x-axis
p2 p1 p3
X
O(nlogn)
Practical Considerations ▪ The big O notation provides a good theoretical
estimate of algorithm efficiency. However, two
algorithms of the same time complexity are not
necessarily equally efficient. As shown in the
preceding example, both algorithms in Listings 5.6
and 22.2 have the same complexity, but the one
in Listing 22.2 is obviously better practically.