Algorithm analysis - Data Structures and Problem Solving Using Java - page 215

binary search The search method used if the input array has been sorted and is
performed from the middle rather than the end. The binary search is loga-
rithmic because the search range is halved in each iteration. (208)
harmonic numbers The N th harmonic number is the sum of the reciprocals of
the first N positive integers. The growth rate of the harmonic numbers is
logarithmic. (206)
interpolation search A static searching algorithm that has better Big-Oh per-
formance on average than binary search but has limited practicality and a
bad worst case. (212)
linear time algorithm An algorithm that causes the running time to grow as
. If the size of the input increases by a factor of f , then the running
time also increases by a factor of f . It is the preferred running time for an
algorithm. (204)
Little-Oh The notation similar to less than when growth rates are being
considered. (202)
logarithm The exponent that indicates the power to which a number is raised
to produce a given number. For example, the logarithm of N (to the base
2) is the value X such that 2 raised to the power of X equals N . (205)
repeated-doubling principle Holds that, starting at 1, repeated doubling can
occur only logarithmically many times until we reach N . (206)
repeated-halving principle Holds that, starting at N , repeated halving can occur
only logarithmically many times until we reach 1. This process is used to
obtain logarithmic routines for searching. (206)
sequential search A linear search method that steps through an array until a
match is found. (207)
static search Accesses data that is never altered. (207)
subquadratic An algorithm whose running time is strictly slower than qua-
dratic, which can be written as . (202)
worst-case bound A guarantee over all inputs of some size. (203)

O ( N )

oN ( )

common errors

For nested loops, the total time is affected by the product of the loop
sizes. For consecutive loops, it is not.

1.

Do not just blindly count the number of loops. A pair of nested loops that
each run from 1 to

2.

N 2 accounts for ON ( )

O 2 N 2

time.

Do not write expressions such as ( ) or ON 2 ( + N ) . Only the dom-

3.

inant term, with the leading constant removed, is needed.