Analysis of Algorithms
V. Adamchik CSCI 570
Lecture 1 University of Southern California
Review
Reading: chapter 1
Chapter 1.1: Runtime Complexity
The term analysis of algorithms is used to describe approaches to study the performance of computer programs. We interested to find a runtime complexity of a particular algorithm as a function of T(n) that describes a relation between algorithm‘s execution time and the input size n.
Runtime Complexity
In this course we will perform the following types of analysis:
•the worst case complexity •the best case complexity •the average case complexity
•the amortized time complexity
We measure the run time of an algorithm using following asymptotic notations: O, Ω, Θ.
Big-O (upper bound)
For any monotonic functions f, g from the positive
f(n) = O( g(n) )
g(n) eventually dominates f(n)
Formally: there exists a constant c such that for all sufficiently large n: f(n) ≤ c*g(n)
integers to the positive integers, we say
if
Discussion Problem 1
Arrange the following functions in increasing order of growth rate with g(n) following f(n) in your list if and only if f(n) = O(g(n))
log nn, n2, nlog n, n log log n, n1/log n 2log n, log2 n, n√2
Discussion Problem 2
Suppose that f(n) and g(n) are two positive non- decreasing functions such that f(n) = O(g(n)).
Is it true that 2f(n) = O(2g(n) )?
Omega: Ω (lower bound)
For any monotonic functions f, g from the positive
integers to the positive integers, we say
f(n) = Ω( g(n) )
f(n) eventually dominates g(n)
Formally: there exists a constant c such that for all sufficiently large n: f(n) ≥ c*g(n)
if:
Discussion Problem 3
Suppose that f(n) and g(n) are two positive non- decreasing functions such that f(n) = Ω(g(n)).
Is it true that 2f(n) = Ω(2g(n) )?
Theta: Θ
For any monotonic functions f, g from the positive
integers to the positive integers, we say
f(n) = Θ( g(n) )
f(n) = O( g(n) ) and f(n) = Ω( g(n) )
In this class we will be mostly concerned with a big-O notation.
if:
1. n = Ω(n2) ?
2. n = Θ(n + log n) ?
3. log n = Ω(n) ?
4. n2 = Ω(n log n) ?
5. n2logn=Θ(n2)?
6. 3n2 + 4n + 5 = Θ(n2) ?
7. 2n + 100n2 + n100= Ω(n101) ?
8. (1/3)n + 100 = Θ(1) ?
Quickies
Chapter 1.2: Sorting Lower Bound
We will show here that any deterministic comparison- based sorting algorithm must take Ω(n log n) time to sort an array of n elements in the worst-case.
Discussion Problem 4
What is the Big-O runtime complexity of the following function? Give the tightest bound.
void bigOh1(int n): for i=1 to n
j=1;
while j < i
j = j*2;
Discussion Problem 5
What is the Big-O runtime complexity of the following function? Give the tightest bound.
void bigOh2(int[] L, int n) while (n > 0)
find_max(L, n); //finds the max in L[0…n-1] n = n/4;
Discussion Problem 6
What is the Big-O runtime complexity of the following function? Give the tightest bound.
string bigOh3(int n)
if(n == 0) return “a”; string str = bigOh3(n-1); return str + str;
Chapter 1.3: Trees and Graphs
A graph G is a pair (V, E) where V is a set of vertices (or nodes) E is a set of edges connecting the vertices.
An undirected graph is connected when there is a path between every pair of vertices.
A tree is a connected graph with no cycles.
A path in a graph is a sequence of distinct vertices.
A cycle is a path that starts and ends at the same vertex.
We start with reviewing mathematical proofs (induction and contradiction).
Theorem. Let G be a graph with V vertices and E edges. The following statements are equivalent:
1. G is a tree (a connected graph with no cycles).
2. Every two vertices of G are connected by a unique path.
3. G is connected and V = E + 1.
4. G is acyclic and V = E + 1.
5. G is acyclic and if any two non-adjacent vertices are joined by an edge, the resulting graph has exactly one cycle.
Theorem. Prove that in an undirected simple graph G = (V, E), there are at most V(V-1)/2 edges. In short, using the asymptotic notation, E = O(V2).
Representing Graphs
Adjacency List or Adjacency Matrix
Vertex X is adjacent to vertex Y if and only if there is an edge (X, Y) between them.
Adjacency List Representation
34
15 2
Is vertex 1 adjacent to 3?
It takes linear time to figure it out.
52 45
1
2
3
4
5
1 null
4 3
Adjacency Matrix Representation
34
15 2
0100 1 0001 1
1001 0 0000 0 0010 0
Is vertex 1 adjacent to 3?
It takes constant time to figure it out.
Representing Graphs Adjacency List Representation is used for
representation of the sparse (E = O(V)) graphs. Adjacency Matrix Representation is used for
representation of the dense (E = Ω(V2)) graphs. Is the Facebook social graph sparse or dense?
We can say a connected graph is maximally sparse if it is a tree.
We can say a graph is maximally dense if it is complete.
Graph Traversals
Depth-First-Search (DFS) Breadth-First-Search (BFS)
DFS uses a stack for backtracking. BFS uses a queue for bookkeeping.
Runtime complexity: O(V + E)
Perform a DFS on the following graph 1234
8 9 10 11 12
16
567
13 14 15
Perform a BFS on the following graph 1234
8 9 10 11 12
16
567
13 14 15
Discussion Problem 7
The complete graph on n vertices, denoted Kn, is a simple graph in which there is an edge between every pair of distinct vertices.
What is the height of the DFS tree for the complete graph Kn?
What is the height of the BFS tree for the complete graph Kn?