294 INDEX
Quicksort (continued)
splitting the list, 90-91
worst-case analysis of, 91
R
Radix sort, 58, 73-76
analysis, 74-76
chapter study suggestion results, 270
three passes of, 75
Random access machine, 184
Random numbers, 261
Random number table, 259-260
RanNum(), 262
Rates of growth, 20-23
big oh, 22, 23
big omega, 22
big theta, 23
classification of, 22
notation, 23
Records, 42, 95, 97
Recurrence relation, 27, 32-37
for algorithms, 3
for quicksort, 92, 93
Recursion
tournament method based on, 27
Recursive algorithms, 2
for depth-first traversal, 151
and dynamic programming, 252
efficiency, 26-27
and eight queens problem, 247, 249
recurrence relations derived from, 32
Recursive calls, 26
Recursive sort algorithms
merge sort, 83
quicksort, 89
Reductions
and NP-complete problems, 220
problem, 217-218
Reliability, 143
Repetitive algorithms, 2
Ring graph, 163
Ring networks, 181, 182
Roots
and set partitioning, 172, 174
Round-off error, 205
Routers, 143
Rows
and Gauss-Jordan method, 117-119
in matrix, 112, 113
Run construction, 99
Run merge comparisons, 99-100
Run times
and Monte Carlo algorithms, 244S
Satisfiability problems, 219
Scalability, 183, 190
Scheduling, job, 227-228
Search algorithms, 42, 43
Seed value, 261, 262
Selection, 53-55
Sequential algorithms, 188, 205
Sequential matrix multiplication algorithms,
203
Sequential search algorithms, 43-45, 214
average-case analysis of, 44-45
binary, 190, 191
worst-case analysis of, 44
Sequential sort algorithms, 183