# CS代考计算机代写 algorithm Analysis of Algorithms

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?