Introduction

Text Book
 Textbook: Introduction to Algorithms by Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest and
Clifford Stein. 3rd Edition
 Reference: Algorithm Design by Jon Kleinberg and Eva
Tardos. (Published by Addison Wesley).
Introduction
 What is an algorithm?
 An algorithm is an effective method for solving a
problem using a finite sequence of instructions.
 Examples
 sort a list of numbers
 find a route from one place to another (cars, packet routing,
phone routing, ...)
 find the longest common substring between two strings
 microchip wiring/design (VLSI)
 solving sudoku
 cryptography
 compression (file, audio, video)
 pagerank
 classify a web page
Properties of interest
 What properties of algorithms are we interested
in?
 does it terminate?
 is it correct, i.e. does it do what we think it’s supposed
to do?
 what are the computational costs?
 what are the memory/space costs?
 what happens to the above with different inputs?
 how difficult is it to implement and implement
correctly?
Motivation
 Why are we interested?

 Algorithms allow us to design and analyze computer

programs in an abstract manner.

 But most of the algorithms/data structure we will discuss have

been around for a while and are implemented.
 For example, the java.util package has Hashtable, LinkedList, Stack,
TreeSet implementations with the relevant algorithms for searching
and sorting.
 Same for C++ Standard Template Library (STL).

 Know what’s out there/possible/impossible

 Know the right algorithm to use
 Tools for analyzing and developing new algorithms

Pseudocode
 A way to discuss how an algorithm works that is language agnostic and without being
encumbered with actual implementation details.
 Should give enough detail for a person to understand, analyze and implement the
algorithm.
Largest_Number (A)
Input: A is a set of integers
Output: return the largest number
• Array indices start at 1

• Shortcuts for simple function

(e.g. swap)

• We’ll use  instead of = for

variable assignment
ReverseOrder (A)
Input: A is a set of integers • Indentation specifies scope
Output: reverse the values of A
Sorting
 What is Sorting?
 Input: An array of numbers A
 Output: The array of numbers in sorted order,

i.e. A[i] ≤ A[j] for all i < j

 For example:
 15 , 9 , 2, 3, 1, 20 , 25, 14 (input)
 1 , 2 , 3, 9 , 14, 15, 20, 25 (sorted output)
Insertion Sort (A)
Input: A is a set of unsorted integer values
Output: Sorted set
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Insertion Sort

Running Time equation

Insertion Sort
Bubble Sort
Asymptotic Notation
Reading
 The reading for this lecture is Chapter 3 (complete)
Asymptotic notation
 How do you answer the question: “what is the
running time of algorithm x?”
 We need a way to talk about the computational cost
of an algorithm that focuses on the essential parts
and ignores irrelevant details
 We’ve seen some of this already:
 linear
 n log n
 n2
Asymptotic notation
 Precisely calculating the actual steps is
tedious and not generally useful (we did this
last time)
 Different operations take different amounts of

time. Even from run to run, things such as

caching, etc. cause variations
 Want to identify categories of algorithmic

runtimes
For example…
f (n) takes n2
steps
1

f (n) takes 3n + 100 steps

2

f (n) takes 2n+1 steps

3

 Which algorithm is better?

 Is the difference between f and f
2 3
important/significant?
Runtime examples
Big O: Upper bound
 O(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
O( g (n))  f (n) : 
 0  f (n) cg (n) for all n n0 
Big O: Upper bound
 O(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
O( g (n))  f (n) : 
 0  f (n) cg (n) for all n n0 

We can bound the function

f(n) above by some constant
factor of g(n)
Big O: Upper bound
 O(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
O( g (n))  f (n) : 
 0  f (n) cg (n) for all n n0 

We can bound the function

For some increasing
f(n) above by some constant
range
multiplied by g(n)
Big O: Upper bound
 O(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
O( g (n))  f (n) : 
 0  f (n) cg (n) for all n n0 

2
f1 ( x )  3n
2 f 2 ( x)  1 / 2n 2  100
O(n )  2
f 3 ( x)  n  5n  40
f 4 ( x)  6n
Big O: Upper bound
 O(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
O( g (n))  f (n) : 
 0  f (n) cg (n) for all n n0 

Generally, we’re most interested in

big O notation since it is an upper
bound on the running time
Omega: Lower bound
 Ω(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
( g (n))  f (n) : 
 0 cg (n)  f (n) for all n n0 
Omega: Lower bound
 Ω(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
( g (n))  f (n) : 
 0 cg (n)  f (n) for all n n0 

We can bound the function

f(n) below by some constant
factor of g(n)
Omega: Lower bound
 Ω(g(n)) is the set of functions:
 there exists positive constants c and n0 such that 
( g (n))  f (n) : 
 0 cg (n)  f (n) for all n n0 

2
f1 ( x)  3n
2 f 2 ( x)  1 / 2n 2  100
( n )  2
f 3 ( x)  n  5n  40
3
f 4 ( x)  6n
Theta: Upper and lower bound
 Θ(g(n)) is the set of functions:
 there exists positive constants c1 , c2 and n0 such that 
( g (n))  f (n) : 
 0 c1 g (n)  f (n) c2 g (n) for all n n0 
Theta: Upper and lower bound
 Θ(g(n)) is the set of functions:
 there exists positive constants c1 , c2 and n0 such that 
( g (n))  f (n) : 
 0 c1 g (n)  f (n) c2 g (n) for all n n0 

We can bound the function

f(n) above and below by some
constant factor of g(n) (though
different constants)
Theta: Upper and lower bound
 Θ(g(n)) is the set of functions:
 there exists positive constants c1 , c2 and n0 such that 
( g (n))  f (n) : 
 0 c1 g (n)  f (n) c2 g (n) for all n n0 

Note: A function is theta bounded iff it is big O

bounded and Omega bounded
Theta: Upper and lower bound
 Θ(g(n)) is the set of functions:
 there exists positive constants c1 , c2 and n0 such that 
( g (n))  f (n) : 
 0 c1 g (n)  f (n) c2 g (n) for all n n0 

2
f1 ( x)  3n
2 f 2 ( x)  1 / 2n 2  100
( n )  2
f 3 ( x)  n  5n  40
2
f 4 ( x)  3n  n log n
Visually

f(n)
Visually: upper bound

f(n)

n0
Visually: lower bound

f(n)

n0
worst-case vs. best-case vs.
average-case
 worst-case: what is the worst the running time of the
algorithm can be?
 best-case: what is the best the running time of the
algorithm can be?
 average-case: given random data, what is the
running time of the algorithm?
 Don’t confuse this with O, Ω and Θ. The cases
above are situations, asymptotic notation is about
bounding particular situations
 Proving bounds: find constants
that satisfy inequalities
 Show that 5n2 – 15n + 100 is Θ(n2)
 Step 1: Prove O(n2) – Find constants c and n
0
such that 5n2 – 15n + 100 ≤ cn2 for all n > n0
2
cn  5n 2  15n  100
c  5  15 / n  100 / n 2

Let n0 =1 and c = 5 – 15 + 100 = 90.

100/n2 only get smaller as n increases and -15/n is
negative
Proving bounds
 Step2: Prove Ω(n2) – Find constants c and n0
such that 5n2 – 15n + 100 ≥ cn2 for all n > n0

2
cn  5n 2  15n  100
c  5  15 / n  100 / n 2

Let n0 =4 and c = 5 – 15/4 = 1.25 (or anything less

than 1.25). We can ignore 100/n2 since it is always
positive and 15/n is always decreasing.
Some rules of thumb
 Multiplicative constants can be omitted
 14n2 becomes n2
 7 log n become log n
 Lower order functions can be omitted
 n + 5 becomes n
 n2 + n becomes n2
 na dominates nb if a > b
 n2 dominates n, so n2+n becomes n2
 n1.5 dominates n1.4
Some rules of thumb
 an dominates bn if a > b
 3n dominates 2n
 Any exponential dominates any polynomial
 3n dominates n5
 2n dominates nc
 Any polynomial dominates any logorithm
 n dominates log n or log log n
 n2 dominates n log n
 n1/2 dominates log n
 Do not omit lower order terms of different variables
(n2 + m) does not become n2
Big O
 n2 + n log n + 50

 2n -15n2 + n3 log n

 nlog n + n2 + 15n3

 n5 + n! – nn
Some examples
 O(1)– constant. Fixed amount of work,
regardless of the input size
 add two 32 bit numbers
 determine if a number is even or odd
 sum the first 20 elements of an array
 delete an element from a doubly linked list
 O(logn) – logarithmic. At each iteration,
discards some portion of the input (i.e. half)
 binary search
Some examples
 O(n)– linear. Do a constant amount of work
on each element of the input
 find an item in a linked list
 determine the largest element in an array
 O(nlog n) log-linear. Divide and conquer
algorithms with a linear amount of work to
recombine
 Sort a list of number with MergeSort
 FFT
Some examples
 O(n2) – quadratic. Double nested loops that
iterate over the data
 Insertion sort
 O(2n) – exponential
 Enumerate all possible subsets
 Traveling salesman using dynamic programming
 O(n!)
 Enumerate all permutations
 determinant of a matrix with expansion by minors