Category list

Chapter 2 Algorithms

Algorithms and Data Structures in C++
by Alan Parker
CRC Press, CRC Press LLC
ISBN: 0849371716 Pub Date: 08/01/93

Table of Contents

Chapter 2
Algorithms

This chapter presents the fundamental concepts for the analysis of algorithms.

2.1 Order

N denotes the set of natural numbers , {1, 2, 3, 4, 5, . . .}.

Definition 2.1

A sequence, x , over the real numbers is a function from the natural numbers into the real numbers:

x ₁ is used to denote the first element of the sequence, x (1) In general,

and will be written as

Unless otherwise noted, when x is a sequence and f is a function of one variable, f ( x ), is the sequence obtained by applying the function f to each of the elements of x . If

then

For example,

Definition 2.2

If x and y are sequences, then x is of order at most y , written x ∈ O ( y ), if there exists a positive integer N and a positive number k such that

Definition 2.3

If x and y are sequences then x is of order exactly y , written, x ∈ Θ ( y ), if x ∈ Θ ( y ) and y ∈ O ( x ).

Definition 2.4

If x and y are sequences then x is of order at least y , written, x ∈ Ω ( y ), if y ∈ O ( x ).

Definition 2.5

The time complexity of an algorithm is the sequence

where t _k is the number of time steps required for solution of a problem of size k .

Example 2.1 Time Complexity

The calculation of the time complexity for addition is illustrated in Example 2.1. A comparison of the order of several classical functions is shown in Table 2.1. The time required for a variety of operations on a 100 Megaflop machine is illustrated in Table 2.2. As can be seen from Table 2.1 if a problem is truly of exponential order then it is unlikely that a solution will ever be rendered for the case of n=100. It is this fact that has led to the use of heuristics in order to find a “good solution” or in some cases “a solution” for problems thought to be of exponential order. An example of Order is shown in Example 2.2. through Example 2.4.

**Table 2.1** Order Comparison
Function	n=1	n=10	n=100	n=1000	n=10000
log( n )		3.32	6.64	9.97	13.3
n log ( n )		33.2	664	9.97×10 ³	1.33×10 ⁵
n ²	1	100	10000	1×10 ⁶	1×10 ⁸
n ⁵	1	1×10 ⁵	1×10 ¹⁰	1×10 ¹⁵	1×10 ²⁰
e ⁿ	2.72	2.2×10 ⁴	2.69×10 ⁴³	1.97×10 ⁴³⁴	8.81×10 ⁴³⁴²
n !	1	3.63×10 ⁶	9.33×10 ¹⁵⁷	4.02×10 ²⁵⁶⁷	2.85×10 ³⁵⁶⁵⁹

**Table 2.2** Calculations for a 100 MFLOP machine
Time	# of Operations
1 second	10 ⁸
1 minute	6 × 10 ⁹
1 hour	3.6 × 10 ¹¹
1 day	8.64 × 10 ¹²
1 year	3.1536 × 10 ¹⁵
1 century	3.1536 × 10 ¹⁷
100 trillion years	3.1536 × 10 ²⁹

2.1.1 Justification of Using Order as a Complexity Measure

One of the major motivations for using Order as a complexity measure is to get a handle on the inductive growth of an algorithm. One must be extremely careful however to understand that the definition of Order is “in the limit.” For example, consider the time complexity functions f ₁ and f ₂ defined in Example 2.6. For these functions the asymptotic behavior is exhibited when n ≥ 10 ⁵⁰ . Although f ₁ ∈ Θ ( e ⁿ ) it has a value of 1 for n < 10 ⁵⁰ . In a pragmatic sense it would be desirable to have a problem with time complexity f ₁ rather than f ₂ . Typically, however, this phenomenon will not appear and generally one might assume that it is better to have an algorithm which is Θ (1) rather than Θ ( e ⁿ ). One should always remember that the constants of order can be significant in real problems.