BLG 336E

Analysis of Algorithms II
Lecture 3:
Growth of Functions, Asymptomatic Analysis, Runtimes,
Big-O Notation, Theta, Omega

1
Algorithm Analysis


Thinking about how the resource requirements of the algorithms will
scale with increasing input size.


Resources:

time

space

Computational efficiency. Efficiency in running time.

We want algorithms that run quickly!

2
Computational Tractability

As soon as an Analytic Engine exists, it will necessarily

guide the future course of the science. Whenever any
result is sought by its aid, the question will arise - By what
course of calculation can these results be arrived at by the
machine in the shortest time? - Charles Babbage

Charles Babbage (1864) Analytic Engine (schematic)

3
How to measure complexity?
• Accurate running time is not a good measure
• It depends on input
• It depends on the machine you used and who
implemented the algorithm

• We would like to have an analysis that does not

depend on those factors

FROM AoA I!!

4
Machine-independent
• A generic uniprocessor random-access machine
(RAM) model
• No concurrent operations
• Each simple operation (e.g. +, -, =, *, if, for) takes 1 step.
• Loops and subroutine calls are not simple operations.
• All memory equally expensive to access
• Constant word size
• Unless we are explicitly manipulating bits
• No memory hierarchy (caches, virtual mem) is modeled

FROM AoA I!!

5
Running Time
• Running Time:T(n): Number of primitive
operations or steps executed for an input of size n.
• Running time depends on input
• already sorted sequence is easier to sort
• Parameterize running time by size of input
• short sequences are easier to sort than long ones
• Generally, we seek upper bounds on running time
• everybody likes a guarantee

FROM AoA I!!

6
Kinds of Analysis
• Worst-case: (usually)
• T(n) = maximum time of algorithm on any input of size n
• Average-case: (sometimes)
• T(n) = expected time of algorithm over all inputs of size n
• Need assumption about statistical distribution of inputs
• Best-case: (difficult to determine)
• Cheat with a slow algorithm that works fast on some input

FROM AoA I!!

7
Worst-Case Analysis

Worst case running time. Obtain bound on largest possible running

time of algorithm on input of a given size N.

Generally captures efficiency in practice.

Draconian view**, but hard to find effective alternative.

Average case running time. Obtain bound on running time of algorithm

on random input as a function of input size N.

Hard (or impossible) to accurately model real instances by random
distributions.

Algorithm tuned for a certain distribution may perform poorly on
other inputs.

**1. Designating a law or code of extreme severity. 2. Harsh, rigorous.

8
Brute-Force Search

Brute force. For many non-trivial problems, there is a natural brute

force search algorithm that checks every possible solution.

Typically takes 2N time or worse for inputs of size N.

Unacceptable in practice.
n ! for stable matching
with n men and n women


Not only too slow to be useful, it is an intellectual cop-out.

Provides us with absolutely no insight into the structure of the
problem.

Proposed definition of efficiency. An algorithm is efficient

if it achieves qualitatively better worst-case performance
than brute-force search.

9
Exhaustive Search is Slow!
• Because it tries all n! permutations, it is much slower
to use when there are more than 10-20 points. [For
n=1000, will not be achieved in your lifetime!]

• No efficient, correct algorithm exists for the

travelling salesman problem.

• Conclusions: The example shows the importance of

the 4 questions we ask about algorithms. It also
shows that they are very much related!
1. How to devise algorithms?
2. How to validate/verify algorithms?
3. How to analyze algorithms?
4. How to test a program?
Polynomial-Time

Desirable scaling property. When the input size doubles, the algorithm
should only slow down by some constant factor C.

There exists constants c > 0 and d > 0 such that on every

input of size N, its running time is bounded by cN d steps.

A step. a single assembly-language instruction, one line of a

programming language like C…

What happens if the input size increases from N to 2N?

Def. An algorithm is poly-time if the above scaling property holds.

11
Polynomial-Time

Desirable scaling property. When the input size doubles, the algorithm
should only slow down by some constant factor C.

There exists constants c > 0 and d > 0 such that on every

input of size N, its running time is bounded by cN d steps.

A step. a single assembly-language instruction, one line of a

programming language like C…

What happens if the input size increases from N to 2N?

Answer: runningtime=c(2N)d=c2dNd =O(Nd) (because d is const)

Def. An algorithm is poly-time if the above scaling property holds.

12
Worst-Case Polynomial-Time

Def. An algorithm is efficient if its running time is polynomial.

Justification: It really works in practice!


Although 6.02  1023  N20 is technically poly-time, it would be
useless in practice.

In practice, the poly-time algorithms that people develop almost
always have low constants and low exponents.

Breaking through the exponential barrier of brute force typically
exposes some crucial structure of the problem.

Exceptions.

Some poly-time algorithms do have high constants and/or
exponents, and are useless in practice.

Some exponential-time (or worse) algorithms are widely used
because the worst-case instances seem to be rare.

13
Why It Matters

Note: Stirling’s approxımation:

14
Asymptotic Order of Growth


We try to express that an algorithm’s worst case running time is at
most proportional to some function f(n).

Function f(n) becomes a bound on the running time of the algorithm.


Pseudo-code style.

counting the number of pseudo-code steps.

step. Assigning a value to a variable, looking up an entry in an array,
following a pointer, a basic arithmetic operation…

“On any input size n, the algorithm runs for at most 1.62n 2 + 3.5n + 8
steps.”

Do we need such precise bound?

We would like to classify running times at a coarser level of granularity.

Similarities show up more clearly.


15
Big-Oh Notation

16
Asymptotic Analysis

17
Example: One-Loop

A. O(1)
B. O(n)
C. O(logn)
D. O(n2)

18
Example: Two-Loops

A. O(1)
B. O(n)
C. O(logn)
D. O(n2)

19
Example: Two Nested Loops

A. O(1)
B. O(n)
C. O(logn)
D. O(n2)

20
Example: Two Nested Loops II

A. O(1)
B. O(n)
C. O(logn)
D. O(n2)

21
Big-Oh Definition

22
Big-Oh formal Definition

23
Example 1

24
Omega Notation

25
Theata Notation

c2∙g(n)

Running Time (t)

f(n)
c1∙g(n)

n0 Input Size (n)

26
Little o: Definition
• For a given function g(n), o(g(n)) is the set of
functions:
o(g(n))= {f(n): for any positive constant c,
there exists a constant n0
such that 0 ≤ f(n) < c g(n)
for all n ≥ n0 }

27
Little o
• Note the < instead of ≤ in the definition of Little-o:
0 ≤ f(n) < c g(n) for all n ≥ n0
• Contrast this to the definition used for Big-O:
0 ≤ f(n) ≤ c g(n) for all n ≥ n0
• Little-o notation denotes an upper bound that is not
asymptotically tight. We might call this a loose
upper bound.
• Examples: 2n  o(n2) but 2n2  o(n2)

28
Little o: Definition
• Given that f(n) = o(g(n)), we know that g grows
strictly faster than f. This means that you can
multiply g by a positive constant c and beyond n0, g
will always exceed f.
• No graph to demonstrate little-o, but here is an
example:
n2 = o(n3) but
n2 ≠ o(n2).
Why? Because if c = 1, then f(n) = c g(n), and the
definition insists that f(n) be less than c g(n).

29
Little omega: Definition
• For a given function g(n), (g(n)) is the set of
functions:
(g(n))= {f(n): for any positive constant c,
there exists a constant n0
such that 0 ≤ c g(n) < f(n)
for all n ≥ n0 }

30
Little omega: Definition
• Note the < instead of ≤ in the definition:
0 ≤ c g(n) < f(n)
• Contrast this to the definition used for Big-:
0 ≤ c g(n) ≤ f(n)
• Little-omega notation denotes a lower bound that is
not asymptotically tight. We might call this a loose
lower bound.
• Examples:
n  (n2) n( ) n n (lg n)

31
Little omega
• No graph to demonstrate little-omega, but here is
an example:
n3 is (n2) but
n3 ≠ (n3).
Why? Because if c = 1, then f(n) = c g(n), and the
definition insists that c g(n) be strictly less than f(n).

32
Asymptotic Notation
c2∙g(n)
c∙g(n)

Running Time (t)

Running Time (t)

f(n)
f(n)
c1∙g(n)

n0 n0
Input Size (n) Input Size (n)

Big O Big Theta

Running Time (t)

f(n)
c∙g(n)

n0 Big
Input Size (n)
Omega
33
Example

34
Where does this notation come from??

35
Asymptotic Order of Growth

Upper bounds. T(n) is O(f(n)) if there exist constants c > 0 and n 0  0

such that for all n  n0 we have T(n)  c · f(n).

Lower bounds. T(n) is (f(n)) if there exist constants c > 0 and n 0  0

such that for all n  n0 we have T(n)  c · f(n).

Tight bounds. T(n) is (f(n)) if T(n) is both O(f(n)) and (f(n)).

Ex: T(n) = 32n2 + 17n + 32.


T(n) is O(n2), O(n3), (n2), (n), and (n2) .

T(n) is not O(n), (n3), (n), or (n3).

36
Asymptotically Tight Bounds

How to prove that f(n) is (g(n))?

Answer:
If the following limit exists and is equal to a constant c>0, then f(n) is (g(n)).
f ( n)
lim
n  g ( n )

Or
show that f(n) is both O(g(n)) and (g(n))

37
Notation

Slight abuse of notation. T(n) = O(f(n)).


Asymmetric:
– f(n) = 5n3; g(n) = 3n2
– f(n) = O(n3) = g(n)
– but f(n)  g(n).

Better notation: T(n)  O(f(n)).

Meaningless statement. Any comparison-based sorting algorithm

requires at least O(n log n) comparisons.

Statement doesn't "type-check."

Use  for lower bounds.

38
Properties

Transitivity.

If f = O(g) and g = O(h) then f = O(h).

If f = (g) and g = (h) then f = (h).

If f = (g) and g = (h) then f = (h).

Additivity.

If f = O(h) and g = O(h) then f + g = O(h).

If f = (h) and g = (h) then f + g = (h).

If f = (h) and g = (h) then f + g = (h).

Please see the proofs in the book pp. 39+.

39
Asymptotic Bounds for Some Common Functions

Polynomials. a0 + a1n + … + adnd is (nd) if ad > 0.

Polynomial time. Running time is O(nd) for some constant d independent

of the input size n. (even if d is not an integer.)
(Note that running time is also (nd). See book for the proof.)

Logarithms. O(log a n) = O(log b n) for any constants a, b > 0.

can avoid specifying the

Very slowly growing functions.
base

Logarithms. For every x > 0, log n = O(nx).

log grows slower than every polynomial

Exponentials. For every r > 1 and every d > 0, nd = O(rn).

every exponential grows faster than every polynomial

40
2.4 A Survey of Common Running Times
Linear Time: O(n)

Linear time. Running time is at most a constant factor times the size
of the input.

Computing the maximum. Compute maximum of n numbers a1, …, an.

max  a1
for i = 2 to n {
if (ai > max)
max  ai
}

42
Linear Time: O(n)

Merge. Combine two sorted lists A = a1,a2,…,an with B = b1,b2,…,bn

into sorted whole.

i = 1, j = 1
while (both lists are nonempty) {
if (ai  bj) append ai to output list and increment i
else(ai  bj)append bj to output list and increment j
}
append remainder of nonempty list to output list

Claim. Merging two lists of size n takes O(n) time.

Pf. After each comparison, the length of output list increases by 1.

43
O(n log n) Time

O(n log n) time. Arises in divide-and-conquer algorithms.

also referred to as linearithmic time

Sorting. Mergesort and heapsort are sorting algorithms that perform

O(n log n) comparisons.

Largest empty interval. Given n time-stamps x1, …, xn on which copies

of a file arrive at a server, what is largest interval of time when no
copies of the file arrive?

O(n log n) solution. Sort the time-stamps. Scan the sorted list in
order, identifying the maximum gap between successive time-stamps.

44
Quadratic Time: O(n2)

Quadratic time. Enumerate all pairs of elements.

Closest pair of points. Given a list of n points in the plane (x1, y1), …,
(xn, yn), find the pair that is closest.

O(n2) solution. Try all pairs of points.

min  (x1 - x2)2 + (y1 - y2)2

for i = 1 to n {
for j = i+1 to n {
d  (xi - xj)2 + (yi - yj)2 don't need to
take square roots
if (d < min)
min  d
}
}

Remark. (n2) seems inevitable, but this is just an illusion. see chapter 5

45
Cubic Time: O(n3)

Cubic time. Enumerate all triples of elements.

Set disjointness. Given n sets S1, …, Sn each of which is a subset of

1, 2, …, n, is there some pair of these which are disjoint?

O(n3) solution. For each pairs of sets, determine if they are disjoint.

foreach set Si {
foreach other set Sj {
foreach element p of Si {
determine whether p also belongs to Sj
}
if (no element of Si belongs to Sj)
report that Si and Sj are disjoint
}
}

46
Polynomial Time: O(nk) Time

Independent set of size k. Given a graph, are there k nodes such that
no two are joined by an edge? k is a constant

O(nk) solution. Enumerate all subsets of k nodes.

for each subset S of k nodes {

check whether S in an independent set
if (S is an independent set)
report S is an independent set
}
}


Check whether S is an independent set = O(k2).

Number of k element subsets =

O(k2 nk / k!) = O(nk).
poly-time for k=17,
but not practical

47
Exponential Time

Independent set. Given a graph, what is maximum size of an

independent set?

S*  
for each subset S of nodes {
check whether S in an independent set
if (S is largest independent set seen so far)
update S*  S
}
}

O(n2 2n) solution. Enumerate all subsets.

Total number of subsets: 2n.

48
Sublinear Time

Binary search of a sorted list: O(log2n)

49
Recap: factorial, exponential
Number of operations 
slower

inputs
Number of
Time Versus Space Complexities
Two main characteristics for programs
• Time complexity: ≈ CPU usage
• Space complexity: ≈ RAM usage

NB: if time complexity is “high” your algorithm may

run for too long; if space complexity is high, your
stack may be over flown, and you may not be able to
run the algorithm at all!
Space and Time complexity

• The space complexity of an algorithm is the amount of memory

it needs to run to completion.

• The time complexity of an algorithm is the amount of computer

time it needs to run to completion.
Data Structure Used May Affect Complexity

Gale Shapley Algorithm (2.3) needs to maintain a dynamically changing

set (list of free men).
Need fast ADD, DELETE-MAX, SELECT-MAX OPERATIONS
Use Priority Queue Data Structure.

Two implementations of priority queues:

1) Using Arrays and Lists: Slower: O(n 2)

2) Using Heap: Faster: O(nlogn)

54
Heap
A binary tree with n nodes and of height h is
almost complete iff its nodes correspond to the
nodes which are numbered 1 to n in the complete
binary tree of height h.
A heap is an almost complete binary tree that
satisfies the heap property:
max-heap: For every node i other than the root:
A[Parent(i)] ≥ A[i]
min-heap: For every node i other than the root:
A[Parent(i)] ≤ A[i]
Max-Heap
A max-heap is an almost complete binary tree that
satisfies the heap property:
For every node i other than the root,
A[PARENT(i)] ≥ A[i]
What does this mean?
 the value of a node is at most the value of its
parent
 the largest element in the heap is stored in the
root
 subtrees rooted at a node contain smaller values
than the node itself
57
Propose-And-Reject Algorithm (Gale Shapley)

Propose-and-reject algorithm. [Gale-Shapley 1962] Intuitive method

that guarantees to find a stable matching.

Initialize each person to be free.

while (some man is free and hasn't proposed to every woman) {
Choose such a man m
w = 1st woman on m's list to whom m has not yet proposed
if (w is free)
assign m and w to be engaged
else if (w prefers m to her fiancé m')
assign m and w to be engaged, and m' to be free
else
w rejects m
}

58
Implementing the Gale Shapley Algorithm

Using Priority Queues (Heap):

There is a need to keep a dynamically changing set (e.g. The set of free
men)
We need to add, delete-max, select-max elements from the list fast.
Priority queue: Elements have a priority or key, each time you select,
you select the item with the highest priority.
A set of elements S
Each element v in S has an associated key value key(v)
Add, delete, search operations in O(logn) time.
A sequence of O(n) priority queue ops can be used to sort n numbers.
An implementation for a priority queue: Heap
Heap order: key(w)<=key(v) where v at node i and w at i’s parent
Heap operations:
StartHeap(N), Insert(H,v), FindMin(H), Delete(H,i), ExtractMin(H),
ChangeKey(H,v,α)

59
Take-home lesson

The heart of any algorithm is an idea.

Efficiency and correctness are to be taken into account.
There are some correct algorithms that are too impractical to compute.
There are laws saying what we can and what we can’t compute!
As a programmer, you have to be aware of such “big” laws. (Cf. engineers
have to know there are laws of physics)
In second part of the course, many problems will be fundamentally hard…

Good news: understanding of basic laws such as

multiplication principle will take you a long way.
Next Lecture


Basics of Graphs

Breadth First Search

Depth First Search

Testing Bi-partite

Topological Ordering

61