Chapter 1: Algorithms:

Efficiency, Analysis, and Order

1
Contents
1.1 Algorithms
1.2 The Importance of Developing Efficient
Algorithms
1.2.1 Sequential Search vs. Binary Search
1.2.2 The Fibonacci Sequence
1.3 Analysis of Algorithms
1.3.1 Time Complexity Analysis
1.3.2 Applying the Theory
1.4 Order
1.4.1 An Intuitive Introduction to Order
1.4.2 A Rigorous Introduction to Order

2
1.1 Algorithms
◼ Problem
◼ Ex. 1.1: Sorting - Sort the list S of n numbers in
nondecreasing order. The answer is the numbers in
sorted sequence.
◼ Ex. 1.2: Searching - Determine whether the number
x is in the list S of n numbers. The answer is yes if x
is in S and no if it is not.
◼ Ex) Partition – Decide whether a given multiset
A= {a1, … , an} of n positive integers has a partition P
such that  ai =  ai
iP iP

3
Parameters, Instance, and Solution

◼ Problem may contain Parameters

◼ Ex. 1.1 - Sorting : S, n
◼ Ex. 1.2 - Searching: S, n, x
◼ Ex) Partition: A, n
◼ Instance of a problem: each specific assignment
of values to parameters
◼ Ex. 1.3: Instance of Sorting
◼ S = [10, 7, 11, 5, 13, 8] and n = 6
◼ Ex. 1.4: Instance of Searching
◼ S = [10, 7, 11, 5, 13, 8], n = 6, and x = 5
◼ Instance of Partition
◼ A = {10, 7, 11, 5, 13, 8} and n = 6 → sol = ‘no’
◼ A = {10, 7, 11, 5, 15, 8} and n = 6 → sol = ‘yes’
◼ Solution
4
Algorithm

◼ Step by step procedure for producing the

solution to each instance
◼ Def.(S. Sahni): An algorithm is a finite set of
instructions that accomplish a particular task.
◼ Input – zero or more
◼ Output - zero or more
◼ Definiteness – each instruction is clear and
unambiguous
◼ Ex) add 6 or 7 to x (X)
◼ Finiteness: must terminate after a finite number of
steps.
◼ cf) procedure
◼ OS (X)
5
Pseudocode and Program

◼ Effectiveness: each instruction must be very basic

so that it can be carried out by a person using
pencil and paper. It also must be feasible.
◼ Integer arithmetic (O)
◼ Real arithmetic (X) – decimal expansion might be
infinitely long
◼ Pseudocode: C++ like
◼ Program: expression of an algorithm in a PL

6
1.2 Importance of Developing Efficient
Algorithms

◼ 1.2.1 Sequential search vs. Binary search

◼ Algorithm 1.1 vs. Algorithm 1.5
◼ # of comparisons (worst case)
◼ n vs. log 2 n + 1

◼ See Table 1.1

7
Algorithm 1.1 Sequential Search

◼ Problem: Is the key x in the array S of n keys?

◼ Input (parameters): positive integer n, array of keys S
indexed from 1 to n, and a key x.
◼ Output: location, the location of x in S (0 if x is not in S)
void seqsearch ( int n,
const keytype S[ ],
keytype x,
index& location)
{
location = 1;
while (location <= n && S[location] != x)
location ++;
if (location > n )
location = 0;
}
8
Algorithm 1.5 Binary Search (1/2)

◼ Problem: Determine whether x in the sorted

array S of n keys.
◼ Inputs: positive integer n, sorted
(nondecreasing order) array of keys S indexed
from 1 to n, and a key x.
◼ Outputs: location, the location of x in S (0 if x
is not in S)

9
Algorithm 1.5 Binary Search (2/2)
void binsearch ( int n,
const keytype S[ ],
keytype x,
index& location)
{
index low, high, mid;
low = 1; high = n;
location = 0;
while (low <= high && location == 0) {
mid = (low + high) / 2;
if (x == S[mid])
location = mid;
else if (x < S[mid])
high = mid – 1
else
low = mid + 1;
}
}
10
1.2.2 Fibonacci Sequence

f 0 = 0,
f1 = 1,
f n = f n −1 + f n − 2 ( n  2 )

◼ Algorithm 1.6 (recursive algorithm)

divide & conquer

11
Algorithm 1.6 n-th Fibonacci Term (Recursive)

◼ Problem: Determine the n-th term in the Fibonacci

Sequence.
◼ Inputs: a nonnegative integer n.
◼ Outputs: fib, the n-th term of the Fibonacci Sequence.
int fib (int n)
{
if (n <= 1)
f 0 = 0, f1 = 1,
return n; f n = f n −1 + f n − 2 ( n  2 )
else
return fib(n-1) + fib(n-2);
}
12
◼ T(n): # of terms in the
recursion tree for n.
T(n) > 2 x T(n-2)
> 2 x 2 x T(n-4)
 2x
2 x
 
x 2 x T (0)
n/2 terms

 T ( n)  2 n/2
(proof by induction in Th. 1.1)

13
Algorithm 1.7 n-th Fibonacci Term (Iterative)
◼ Problem: Determine the n-th term in the Fibonacci
Sequence.
◼ Inputs: a nonnegative integer n.
◼ Outputs: fib2, the n-th term in the Fibonacci Sequence.
int fib2 (int n)
{
index i;
int f[0..n]; ◼ dynamic programming:
f[0] = 0; compute (n+1) terms
if (n > 0) {
f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i – 1] + f[i – 2];
}
return f[n];
}
14
15
1.3 Analysis of Algorithms

◼ Efficiency
◼ Space complexity: memory

◼ Time complexity: execution time

16
1.3.1 Time Complexity Analysis
◼ Want a measure independent of
◼ Computer
◼ Programming language
◼ Programmer
◼ Complex details of algorithms (pointer setting,
incrementing of loop indices)
◼ Not want # of CPU cycles or instructions
◼ Ex) binary search is more efficient than sequential
search
◼ # of comparisons: log n < n
◼ Algorithm’s efficiency: # of basic operations
executed as a function of input size
17
Algorithm 1.2 Add Array Members
◼ Problem: Add all the numbers in the array S of n
numbers.
◼ Inputs: positive integer n, array of numbers S indexed
from 1 to n.
◼ Outputs: sum, the sum of the numbers in S.

number sum (int n, const number S[ ])

{
index i;
number result;
result = 0;
for (i = 1; i <= n ; i++)
result = result + S[i];
return result;
}

18
Algorithm 1.3 Exchange Sort
◼ Problem: Sort n keys in nondecreasing order.
◼ Inputs: positive integer n, array of keys S indexed
from 1 to n.
◼ Outputs: the array S containing the keys in
nondecreasing order.

void exchangesort (int n, keytype S[ ])

{
index i, j;
for (i = 1; i <= n -1; i++)
for (j = i+1; j <= n; j++)
if (S[j] < S[i])
exchange S[i] and S[j];
}

19
Algorithm 1.4 Matrix Multiplication
◼ Problem: Determine the product of two n x n matrices.
◼ Inputs: a positive integer n, 2D arrays of numbers A and B, each
of which has both its rows and columns indexed from 1 to n.
◼ Outputs: a 2D array of numbers C, which has both its rows and
columns indexed from 1 to n, containing the product of A and B.
void matrixmult ( int n,
const number A[ ] [ ],
const number B[ ] [ ],
number C[ ] [ ])
{
index i, j, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
C[i][j] = 0; /* b.o. → e.t. = a
for (k = 1; k <= n; k++)
C[i][j] = C[i][j] + A[i][k] * B[k][j]; /* b.o. → e.t. = b
}
}
20
Input size and Basic operation

◼ Input size
◼ Sequential search, binary search, add array
members, exchange sort: array S of n keys
◼ Matrix multiplication: n, # of rows and columns
◼ Graph: n, e, # of nodes and edges
◼ Fibonacci number:  log n  + 1, # of binary digits to
encode n (n is input not input size)
◼ Basic operation
◼ Single instruction or group of instructions
◼ Execution time is independent of n
◼ Ex) search: comparison

21
 for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
Example C[i][j] = 0; /* b.o. → e.t. = a
for (k = 1; k <= n; k++)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
/* b.o. → e.t. = b
◼ Ex) matrix multiplication }

◼ Execution time → see Algorithm 1.4

◼ Discussion
(1) a  n + b  n
2 3

n = 10 → a  10 + b  10  b  10
2 3 3
◼

n = 100 → a  10 + b  10  b  10
4 6 6
◼

(2) Ignore the time for incrementing loop indices

(3) No time difference
◼ temp = A[i][k] * B[k][j];
◼ C[i][j] = C[i][j] + temp

22
Time Complexity Analysis

◼ Determination of how many times the basic operations

is done for each value of the input size.
◼ In some cases, depends not only the input size but also
on the input value
◼ Ex) sequential search
◼ Best case B(n) = 1
◼ Worst case W(n) = n n 1
◼ Average case A(n) = (n+1)/2   ( k  )
k =1 n
◼ Ex) array add
◼ Every case T(n) = n
◼ Ex) Exchange sort
◼ T(n) = (n-1) + (n-2) + … + 1 = (n-1)n/2
◼ Ex) matrix multiplication T ( n) = n 3
◼ If T(n) exists T(n) = W(n) = A(n) = B(n)
If not W(n), A(n)
23
Space Complexity Analysis

◼ Fixed part that is independent of I/O characteristics

◼ Instruction (code) space
◼ Simple variable x = 3
◼ Constants
◼ Fixed size component variables (A[10], …)
◼ Variable part
◼ Variables depending on input size
Ex : S[n], A[n][n]
◼ Recursion stack (formal parameters, local variables, return
address): space ≥ 3(n+1) words, n is depth of recursion
Ex : Fibonacci number (Alg. 1.6): proportional to n

24
1.3.2 Applying the Theory

◼ Alg. A B
◼ T(n) n n2

◼ b.o. execution time 1000t t

 
 =  2
n  1000 t   n  t
 
? 

25
1.4 Order
◼ 1.4.1 An Intuitive Introduction to Order
◼ a, b, c, d: constants
an + b  ( n) linear
an 2 + bn + c  ( n 2 ) quadratic
an 3 + bn 2 + cn + d  ( n 3 ) cubic

ignore low order terms – see table 1.3

(log n) ( n) ( n log n) ( n 2 ) ( n 3 ) ( 2n )

◼ See figure 1.3

◼ See table 1.4

26
27
28
1.4.2 A Rigorous Introduction to Order
◼ Def. Big O: for a given complexity function f(n), O(f(n))
is the set of complexity functions g(n) for which there
exists some positive real constant c and some
nonnegative integer N s.t. for all n ≥ N,
g(n)  c  f(n) : asymptotic upper bound

g(n)  O(f(n)) g(n) is big O of f(n)

◼ Ex) n 2 + 10n  2 n 2 n  10 n 2 + 10n  O ( n 2 )

g( n) c f ( n) N

n  1  n2 n1 n  O( n 2 )
1
n( n − 1) / 2  n 2 n0 n( n − 1) / 2  O( n 2 )
2

◼ See Figure 1.5 and 1.4

29
30
31
Omega

◼ Def. Omega: for a given complexity function f(n), Ω(f(n))

is the set of complexity functions g(n) for which there
exists some positive real constant c and some
nonnegative integer N s.t. for all n ≥ N,
g(n)  c  f(n) : asymptotic lower bound

g(n)  (f(n)) g(n) is omega of f(n)

◼ Ex) n 2 + 10n  n 2 n0 n 2 + 10n  ( n 2 )

1
n( n − 1) / 2  n 2 n2 n( n − 1) / 2  ( n 2 )
4
n3  1  n2 n1 n 3  ( n 2 )

32
Order

◼ Def. Order: for a given complexity function f(n)

( f ( n)) = O( f ( n))  ( f ( n))

( f ( n))
is the set of complexity functions g(n) for which
there exists some positive real constant c and d and
some nonnegative integer N s.t. for all n ≥ N,
c  f(n)  g(n)  d  f(n)

g(n)  (f(n)) g(n) is order of f(n)

Ex) n( n − 1) / 2  ( n )
2
◼

◼ See Figure 1.6

33
34
Small o

◼ Def. Small o: for a given complexity function f(n), o(f(n))

is the set of complexity functions g(n) satisfying the
following: For every positive real constant c there exists
a nonnegative integer N s.t. for all n ≥ N,
g(n)  c  f(n)

g(n)  o(f(n)) g(n) is small o of f(n)

g(n) is eventually much better function than f(n)

1
◼ Ex) n  c n2 for n 
g( n) f ( n) c
N

35
 Theorem 1.2
If g( n)  o( f ( n)) then g( n)  O( f ( n)) − ( f ( n))
That is, g(n) is in O(f(n)) but not in ( f ( n))

O( f ( n))
more ( f ( n)) more
efficient complex
o( f ( n)) ( f ( n))

◼ Note that o( f ( n))  O( f ( n)) − ( f ( n))

→ see ex. 1.20.

But equality holds for the time complexities of actual
algorithms.

36