Page 253 - Discrete Mathematics and Its Applications

232 3 / Algorithms

Key Terms and Results

TERMS greedy algorithm: an algorithm that makes the best choice at
each step according to some specified condition
algorithm: a finite sequence of precise instructions for per-
forming a computation or solving a problem tractable problem: a problem for which there is a worst-case
searching algorithm: the problem of locating an element in a polynomial-time algorithm that solves it
list intractable problem: a problem for which no worst-case
linear search algorithm: a procedure for searching a list ele- polynomial-time algorithm exists for solving it
ment by element solvable problem: a problem that can be solved by an algo-
binary search algorithm: a procedure for searching an or- rithm
dered list by successively splitting the list in half unsolvable problem: a problem that cannot be solved by an
sorting: the reordering of the elements of a list into prescribed algorithm
order
f(x)is O(g(x)): the fact that |f(x)|≤ C|g(x)| for all x> k
for some constants C and k RESULTS
witness to the relationship f(x)is O(g(x)): a pair C and k linear and binary search algorithms: (given in Section 3.1)
such that |f(x)|≤ C|g(x)| whenever x> k bubble sort: a sorting that uses passes where successive items
f(x)is (g(x)): the fact that |f(x)|≥ C|g(x)| for all x> k are interchanged if they in the wrong order
for some positive constants C and k
insertion sort: a sorting that at the jth step inserts the jth el-
f(x)is (g(x)): the fact that f(x) is both O(g(x)) and (g(x))
ement into the correct position in in the list, when the first
time complexity: the amount of time required for an algorithm
j − 1 elements of the list are already sorted
to solve a problem
space complexity: the amount of space in computer memory
The linear search has O(n) worst case time complexity.
required for an algorithm to solve a problem
The binary search has O(log n) worst case time complexity.
worst-case time complexity: the greatest amount of time re- 2
The bubble and insertion sorts have O(n ) worst case time
quired for an algorithm to solve a problem of a given size
complexity.
average-case time complexity: the average amount of time
required for an algorithm to solve a problem of a given size log n! is O(n log n).
algorithmic paradigm: a general approach for constructing If f 1 (x) is O(g 1 (x)) and f 2 (x) is O(g 2 (x)), then (f 1 + f 2 )(x)
algorithms based on a particular concept is O(max(g 1 (x), g 2 (x))) and (f 1 f 2 )(x) is O((g 1 g 2 (x)).
n
brute force: the algorithmic paradigm based on constructing If a 0 ,a 1 ,...,a n are real numbers with a n = 0, then a n x +
n
algorithms for solving problems in a naive manner from the a n−1 x n−1 + ··· + a 1 x + a 0 is (x ), and hence O(n) and
statement of the problem and definitions (n).
Review Questions
1. a) Define the term algorithm. 4. List these functions so that each function is big-O of
√
3
3
b) What are the different ways to describe algorithms? the next function in the list: (log n) , n /1000000, n,
n 2
n
100n + 101, 3 , n!,2 n .
c) What is the difference between an algorithm for solv-
ing a problem and a computer program that solves this 5. a) How can you produce a big-O estimate for a function
problem? that is the sum of different terms where each term is
the product of several functions?
2. a) Describe, using English, an algorithm for finding the
largest integer in a list of n integers. b) Give a big-O estimate for the function f (n) =
3
n
n
(n!+ 1)(2 + 1) + (n n−2 + 8n n−3 )(n + 2 ).For
b) Express this algorithm in pseudocode.
the function g in your estimate f(x) is O(g(x)) use a
c) How many comparisons does the algorithm use? simple function of smallest possible order.
3. a) State the definition of the fact that f (n) is O(g(n)), 6. a) Define what the worst-case time complexity, average-
where f (n) and g(n) are functions from the set of case time complexity, and best-case time complexity
positive integers to the set of real numbers. (in terms of comparisons) mean for an algorithm that
b) Use the definition of the fact that f (n) is O(g(n)) finds the smallest integer in a list of n integers.
2
directly to prove or disprove that n + 18n + 107 is b) What are the worst-case, average-case, and best-case
3
O(n ). time complexities, in terms of comparisons, of the al-
c) Use the definition of the fact that f (n) is gorithm that finds the smallest integer in a list of n
3
O(g(n)) directly to prove or disprove that n is integers by comparing each of the integers with the
2
O(n + 18n + 107). smallest integer found so far?