Design and Analysis of Algorithms

National University of Computer and Emerging Sciences,

Islamabad
 Algorithm Characteristics
The necessary features of an algorithm:
• Definiteness
• The steps of an algorithm must be precisely defined.
• Effectiveness
• Individual steps are all do-able.
• Finiteness
• It won’t take forever to produce the desired output for any
input in the specified domain.
• Output
• Information or data that goes out.
 Algorithm Characteristics

Other important features of an algorithm:

• Input.
• Information or data that comes in.
• Correctness.
• Outputs correctly relate to inputs.
• Generality.
• Works for many possible inputs.
• Efficiency.
• Takes little time & memory to run.
Complexity Analysis

Want to achieve platform-independence

Use an abstract machine that uses steps of time

and units of memory, instead of seconds or
bytes
 each elementary operation takes 1 step
 each elementary instance occupies 1 unit of
memory
Standard Analysis Techniques

• Constant time statements

• Analyzing Loops
• Analyzing Nested Loops
• Analyzing Sequence of Statements
• Analyzing Conditional Statements
Analysing an Algorithm
• Simple statement sequence
s1; s2; …. ; sk
• Basic Step = 1 as long as k is constant
• Simple loops
for(i=0; i<n; i++) { s; }
where s is Basic Step = 1
• Basic Steps : n
• Nested loops
for(i=0; i<n; i++)
for(j=0; j<n; j++) { s; }
• Basic Steps : n2
Analysing an Algorithm
• Loop index depends on outer loop index
for(j=0;j<=n;j++)
for(k=0;k<j;k++){
s;
}
• Inner loop executed
• 1, 2, 3, …., n times
n n(n+1)
S i =
i=1 2

 Basic Steps : n2
Analysing an Algorithm
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A

int Sum(int A[], int N)

{
int s=0;
for (int i=0; i< N; i++)
s = s + A[i];
return s;
}

How should we analyse this?

Analysing an Algorithm

// Input: int A[N], array of N integers

// Output: Sum of all numbers in array A

int Sum(int A[], int N){

int s=0; 1
for (int i=0; i< N; i++)
2 3 4
s = s + A[i];
5 1,2,8: Once
return s;
6 7
3,4,5,6,7: Once per each iteration
}
8 of for loop, N iteration
Total: 5N + 3
The complexity function of the
algorithm is : f(N) = 5N +3
Constant time statements
• Simplest case: O(1) time statements

• Assignment statements of simple data types

int x = y;

• Arithmetic operations:
x = 5 * y + 4 - z;

• Array referencing:
A[j] = 5;
• Most conditional tests:
if (x < 12) ...
 Analyzing Loops

• Any loop has two parts:

• How many iterations are performed?
• How many steps per iteration?

int sum = 0,j;

for (j=0; j < N; j++)
sum = sum +j;
 Analyzing Loops

• Any loop has two parts:

• How many iterations are performed?
• How many steps per iteration?
int sum = 0,j;
for (j=0; j < N; j++)
sum = sum +j;
• Loop executes N times (0..N-1)
• O(1) steps per iteration
• Total time is N * O(1) = O(N*1) = O(N)
Class Activity
int sum = 0;
for (i=1;i<n; i=i+2)
sum = sum +i;
Class Activity
int sum = 0,j;
for (i=1;i<n; i=i+2)
sum = sum +i;

F(n)= n/2;
F(n)= O(n)
 Analyzing Loops

• What about this for loop?

int sum =0, j;
for (j=0; j < 100; j++)
sum = sum +j;

• Loop executes 100 times

• O(1) steps per iteration
• Total time is 100 * O(1) = O(100 * 1) = O(100) =
O(1)
Analyzing Nested Loops
• Treat just like a single loop and evaluate each
level of nesting as needed:
int j,k;
for (j=0; j<n; j++)
for (k=0; k<n; k++)
sum += k+j;
Analyzing Nested Loops
• Treat just like a single loop and evaluate each
level of nesting as needed:
int j,k; n+1 times
for (j=0; j<n; j++)
for (k=0; k<n; k++) (n) * n+1 times
sum += k+j;
n * n times

F(n)= 2n2+2n+1
F(n)= O(n2)
Analyzing Nested Loops
• Treat just like a single loop and evaluate each
level of nesting as needed:
int j,k;
for (j=0; j<n; j++)
for (k=0; k<n; k++)
sum += k+j;

• Start with outer loop:

• How many iterations? N
• How much time per iteration? Need to evaluate inner
loop

• Inner loop uses O(N) time

• Total time is N * O(N) = O(N*N) = O(N2)
Analyzing Nested Loops
• Treat just like a single loop and evaluate each
level of nesting as needed:
int j,k;
for (j=0; j<N; j++)
for (k=N; k>0; k--)
sum += k+j;
?
Analyzing Nested Loops
• Treat just like a single loop and evaluate each
level of nesting as needed:
int j,k;
for (j=0; j<N; j++)
for (k=N; k>0; k--)
sum += k+j;

• Start with outer loop:

• How many iterations? N
• How much time per iteration? Need to evaluate inner
loop

• Inner loop uses O(N) time

• Total time is N * O(N) = O(N*N) = O(N2)
Analyzing Nested Loops
• Treat just like a single loop and evaluate each
level of nesting as needed:
int j,k;
for (j=0; j<N; j++)
for (k=N; k>0; k--)
sum += k+j;

• Start with outer loop:

• How many iterations? N
• How much time per iteration? Need to evaluate inner
loop

• Inner loop uses O(N) time

• Total time is N * O(N) = O(N*N) = O(N2)
Analyzing Nested Loops

• What if the number of iterations of one

loop depends on the counter of the other?
int j,k;
for (j=0; j < N; j++)
for (k=0; k < j; k++)
sum += k+j;
• Analyze inner and outer loop together:
• Number of iterations of the inner loop is:
• 0 + 1 + 2 + ... + (N-1) = O(N2)
Analyzing Sequence of Statements

for (j=0; j < N; j++)

for (k =0; k < j; k++)
sum = sum + j*k;
for (l=0; l < N; l++)
sum = sum -l;
cout<<“Sum=”<<sum;
Analyzing Sequence of Statements

• For a sequence of statements, compute

their complexity functions individually and
add them up
for (j=0; j < N; j++)
for (k =0; k < j; k++) O(N2)

sum = sum + j*k;

for (l=0; l < N; l++) O(N)
sum = sum -l;
cout<<“Sum=”<<sum; O(1)

Total cost is O(N2) + O(N) +O(1) = O(N2)

SUM RULE
Analysing an Algorithm
• Loop index doesn’t vary linearly
i = 1;
while ( i < n ) {
s;
i = 2 * i;
}
Analysing an Algorithm
• Loop index doesn’t vary linearly
i = 1;
while ( i < n ) {
s;
i = 2 * i;
}
• i takes values 1, 2, 4, … until it exceeds n
i
• 1
• 1x2=2
• 2x2=22
• 22x2=23
• .
• .
• .
• 2k
i • Assume
• 1
• 1x2=2 • i>=n
• 2x2=22 i=2k
• 22x2=23 2k =n
• .
K= log2(n)
• .
• .
• 2k
Analyzing Conditional Statements
What about conditional statements such as

if (condition)
statement1;
else
statement2;
where statement1 runs in O(N) time and statement2 runs in
O(N2) time?

We use "worst case" complexity: among all inputs of size N,

that is the maximum running time?

The analysis for the example above is O(N2)

Analysing an Algorithm

Growth of 5n+3
Estimated running time for different values of N:

N = 10 => 53 steps
N = 100 => 503 steps
N = 1,000 => 5003 steps
N = 1,000,000 => 5,000,003 steps

As N grows, the number of steps grow in linear

proportion to N for this function “Sum”
Some helpful mathematics
• 1+2+3+4+…+N
• N(N+1)/2 = N2/2 + N/2 is O(N2)

• N + N + N + …. + N (total of N times)
• N*N = N2 which is O(N2)

• 1 + 2 + 4 + … + 2N
• 2N+1 – 1 = 2 x 2N – 1 which is O(2N )
106 instructions/sec, runtimes

N O(log N) O(N) O(N log N) O(N2)

10 0.000003 0.00001 0.000033 0.0001

100 0.000007 0.00010 0.000664 0.1000

1,000 0.000010 0.00100 0.010000 1.0

10,000 0.000013 0.01000 0.132900 1.7 min

100,000 0.000017 0.10000 1.661000 2.78 hr

1,000,000 0.000020 1.0 19.9 11.6 day

1,000,000,000 0.000030 16.7 min 18.3 hr 318

centuries
No Need To Be So Exact
Constants do not matter
• Consider 6N2 and 20N2
• When N >> 20, the N2 is what is driving the
function's increase
Lower-order terms are also less important
• N*(N+1)/2 vs.
just N2/2
• The linear term is
inconsequential

We need a better notation for performance that

focuses on the dominant terms only
What Dominates in Previous Example?
What about the +3 and 5 in 5N+3?
• As N gets large, the +3 becomes insignificant
• 5 is inaccurate, as different operations require varying
amounts of time and also does not have any significant
importance

What is fundamental is that the time is linear in N.

Asymptotic Complexity:
Asymptotic Complexity:As NAs
gets large,large,
N gets
concentrate on the highest order term:
concentrate on the highest order term:

 Drop lower order terms such as +3

 Drop the constant coefficient of the highest order term i.e. N
Asymptotic Complexity

• The 5N+3 time bound is said to "grow

asymptotically" like N
• This gives us an approximation of the
complexity of the algorithm
• Ignores lots of (machine dependent)
details, concentrate on the bigger picture
Asymptotic Analysis
• Asymptotic analysis is an analysis of
algorithms that focuses on
• Analyzing problems of large input size
• Consider only the leading term of the formula
• Ignore the coefficient of the leading term
Comparing Functions: Asymptotic Notation

• Big Oh Notation: Upper bound

• Omega Notation: Lower bound
• Theta Notation: Tighter bound
 Big-Oh Rules
• If is f(n) a polynomial of degree d, then f(n) is
O(nd), i.e.,
1. Drop lower-order terms
2. Drop constant factors
• Use the smallest possible class of functions
• Say “2n is O(n)” instead of “2n is O(n2)”
• Use the simplest expression of the class
• Say “3n + 5 is O(n)” instead of “3n + 5 is O(3n)”
Big-Oh Notation
• Given two functions f(n) & g(n) for input n, we
say f(n) is in O(g(n) ) iff there exist positive
constants c and n0 such that

f(n)  c g(n) for all n  n0 g

f
• Basically, we want to find a
n0
function g(n) that is eventually
always bigger than f(n) n
Big-Oh Notation (§3.4)

10,000
• Given functions f(n) 3n

and g(n), we say that 2n+10

1,000
f(n) is O(g(n)) if there
n
are positive constants
100
c and n0 such that
f(n)  cg(n) for n  n0
10
• Example: 2n + 10 is
O(n)
1
• 2n + 10  cn 1 10 100 1,000
• (c  2) n  10 n
• n  10/(c  2)
• Pick c = 3 and n0 = 10
 Showing Order Briefly …
• Show 10N2 + 15N is O(N2)
• .
 Showing Order Briefly …
• Show 10N2 + 15N is O(N2)
• Break into terms.

• 10N2 < 10N2

• 15N < 15N2 for N > 1 (Now add)
• 10N2 + 15N < 10N2 + 15N2 for N > 1
• 10N2 + 15N < 25N2 for N > 1
• c = 25, N0 = 1
• Note, the choices for c and N0 are not unique.
The Gist of Big-Oh
Take functions f(n) & g(n), consider only the
most significant term and remove constant
multipliers:
• 5n+3 → n
• 7n+.5n2+2000 → n2
• 300n+12+nlogn → n log n

Then compare the functions; if f(n) ≤ g(n),

then f(n) is in O(g(n))

43
Big Oh Notation
If f(N) and g(N) are two complexity functions, we say

f(N) = O(g(N))

(read "f(N) as order g(N)", or "f(N) is big-O of g(N)")

if there are constants c and N0 such that for N > N0,
f(N) ≤ c * g(N)
for all sufficiently large N.

*big-O-Upper bound
Comparing Functions
• As inputs get larger, any algorithm of a
smaller order will be more efficient than an
algorithm of a larger order

0.05 N2 = O(N2)
Time (steps)

3N = O(N)

Input (size)
N = 60
Big Omega Notation
Big Theta Notation
Asymptotic notation

• Example:
• f(n) = 3n5+n4 = (n5)
Polynomial and Intractable Algorithms
• Polynomial Time complexity
• An algorithm is said to be polynomial if it is
O( nd ) for some integer d
• Polynomial algorithms are said to be efficient
• They solve problems in reasonable times!

• Intractable algorithms
• Algorithms for which there is no known
polynomial time algorithm
• We will come back to this important class later
 Asymptotic order of growth

A way of comparing functions that ignores

constant factors and small input sizes

• O(g(n)): class of functions f(n) that grow no

faster than g(n)

• Θ(g(n)): class of functions f(n) that grow at same

rate as g(n)

• Ω(g(n)): class of functions f(n) that grow at least

as fast as g(n)
 >=
(g(n)), functions that grow at least as fast as g(n)

=
(g(n)), functions that grow at the same rate as g(n)
g(n)

<=
O(g(n)), functions that grow no faster than g(n)
 Performance Classification
f(n) Classification
1 Constant: run time is fixed, and does not depend upon n. Most instructions are
executed once, or only a few times, regardless of the amount of information being
processed
log n Logarithmic: when n increases, so does run time, but much slower. When n
doubles, log n increases by a constant, but does not double until n increases to n2.
Common in programs which solve large problems by transforming them into smaller
problems.
n Linear: run time varies directly with n. Typically, a small amount of processing is
done on each element.
n log n When n doubles, run time slightly more than doubles. Common in programs which
break a problem down into smaller sub-problems, solves them independently, then
combines solutions
n2 Quadratic: when n doubles, runtime increases fourfold. Practical only for small
problems; typically the program processes all pairs of input (e.g. in a double nested
loop).
n3 Cubic: when n doubles, runtime increases eightfold

2n Exponential: when n doubles, run time squares. This is often the result of a natural,
“brute force” solution.
Size does matter

What happens if we double the input size N?

N log2N 5N N log2N N2 2N
8 3 40 24 64 256
16 4 80 64 256 65536
32 5 160 160 1024 ~109
64 6 320 384 4096 ~1019
128 7 640 896 16384 ~1038
256 8 1280 2048 65536 ~1076
A Display of the Growth of Functions
Commonly Used in Big-O Estimates
Typical Big O Functions – "Grades"
Function Common Name
N! factorial Running
time grows
2N Exponential 'quickly' with
Nd, d > 3 Polynomial more input.
N3 Cubic
N2 Quadratic
N N N Square root N
N log N N log N
N Linear
Running
N Root - n time grows
log N Logarithmic 'slowly' with
more input.
1 Constant
 Review of Three Common Sets

f(n) = O(g(n)) means c  g(n) is an Upper Bound on f(n)

f(n) = (g(n)) means c  g(n) is a Lower Bound on f(n)

f(n) = (g(n)) means c1  g(n) is an Upper Bound on f(n)

and c2  g(n) is a Lower Bound on f(n)

These bounds hold for all inputs beyond some threshold n0.
Properties of the O notation
• Constant factors may be ignored
 " k > 0, kf is O( f)
• Higher powers grow faster
• nr is O( ns) if 0  r  s
Fastest growing term dominates a sum
• If f is O(g), then f + g is O(g)
eg an4 + bn3 is O(n4 )
Polynomial’s growth rate is determined by leading
term
• If f is a polynomial of degree d,
then f is O(nd)
Properties of the O notation
• f is O(g) is transitive
• If f is O(g) and g is O(h) then f is O(h)
• Product of upper bounds is upper bound for the
product
• If f is O(g) and h is O(r) then fh is O(gr)
• Exponential functions grow faster than powers
• nk is O( bn ) " b > 1 and k  0
e.g. n20 is O( 1.05n)
• Logarithms grow more slowly than powers
• logbn is O( nk) " b > 1 and k > 0
e.g. log2n is O( n0.5)
Important!
Properties of the O notation
• All logarithms grow at the same rate
• logbn is O(logdn) " b, d > 1

• Sum of first n rth powers grows as the (r+1)th power

n
 S kr is  ( nr+1 )
k=1
n
e.g. S k = n(n+1) is  ( n2 )
k=1 2
 Order of growth
• We usually consider one algorithm to be more
efficient than another if its worst case running
time has a lower order of growth.
• Due to constant factors and lower order terms, an algorithm
whose running time has a higher order of growth might take
less time for small inputs than an algorithm whose running
time has a lower order of growth. But for large enough
inputs,  ( n2 ) algorithm, for example, will run more
quickly in the worst case than  ( n3 ) algorithm
o-Notation
• Examples
ω- notation