Analysis of Algorithms University of Southern California CSCI 570 V Adamchik Lecture 1 Fall 2023 Review Reading chapter 1 About Myself 1990 2010 was working on Mathematica About Myself 2000 2016 with Carnegie Mellon University Pittsburgh Walking to the sky Bill Gates building for SCS About Myself Since 2016 University of Southern California Los Angeles https viterbi web usc edu adamchik Research My area of research is computer algebra and symbolic computation Computer algebra is the field of math and cs that is concerned with development and implementation of algorithms that allow one to perform specific symbolic mathematical computations like differentiation integration It is spanning many different scientific and technical domains like AI and ML I have published over 70 research articles Chaitin s Omega constant https en wikipedia org wiki Omega constant Bendersky Adamchik s constants 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 that tends to infinity lim Consider a problem of addition of two n bit binary numbers on 64 bit CPU Let T n represent an amount of time used to add two n bit numbers If n 64 addition is performed entirely by CPU We say it takes constant time However for large integers n 64 those numbers do not fit CPU so they have to be added in memory In this case the complexity of addition is a constant anymore but a function of the input size 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 runtime of an algorithm using following asymptotic notations O Big O upper bound For any monotonic functions f g from the positive integers to the positive integers we say f n O g n if g n eventually dominates f n Formally there exist constants c and n0 such that for all sufficiently large n f n c g n c n0 n n n0 f n c g n Example n2 2n 1 O n2 Proof c n0 n n n0 f n c g n We need to find c and n0 Observe that since 1 n we get n2 2 n 1 n2 2 n2 n2 4 n2 for n 1 We choose c 4 and n0 1 Hierarchies of Functions Polynomial functions grow faster than logarithmic functions Exponential functions grow faster than polynomial ones log n O n log2 n O n log1000 n O n n O 2n n10 O 2n n1000 O 2n Discussion Problem 1 Arrange the following functions no formal proof required 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 if f n eventually dominates g n Formally there exist constants c and n0 such that for all sufficiently large n f n c g n c n0 n n n0 f n c g n Example n2 2n 1 n2 c n0 n n n0 f n c g n Proof We need to find c and n0 Observe that n2 2 n 1 n2 for n 1 We choose c 1 and n0 1 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 if Formally c1 c2 n0 n n n0 c1 g n f n c2 g n In this class we will be mostly concerned with a big O notation Quickies 1 2 3 4 5 6 7 8 n n2 n n log n log n n n2 n log n n2 log n n2 3n2 4n 5 n2 2n 100n2 n100 n101 1 3 n 100 1 Discussion Problem 4 Consider the following pseudocode What is the Big O runtime complexity of the following function int FindMax int A int n int max A 0 for int i 1 i n i if max A i max A i return max Among all operations in this code snippet define the most expensive operation and then count how many times it s executed as a function of the input size Discussion Problem 5 Consider the following pseudocode What is the Big O runtime complexity of the following function void bigOh1 int n for int i 1 i n i int j 1 while j i j j 2 Discussion Problem 6 What is the Big O runtime complexity of the following function Give the tightest bound void bigOh2 int A int n while n 0 find max A n finds the max in A 0 n 1 n n 4 Discussion Problem 7 What is the Big O runtime complexity of the following function string bigOh3 int n if n 0 return a string str bigOh3 n 1 return str str concatenation 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 T1 As an example consider an array of three numbers a b c We will sort them by comparisons A tree with six leaves T2 A tree with eight leaves 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 graph is simple if it has no self loops and no multi edges A path in a graph is a sequence of distinct vertices A cycle is a path that starts and ends at the same vertex A tree is a connected graph with no cycles We start with reviewing mathematical proofs induction and contradiction Graph Models A computer network can be modeled using a graph in which the vertices of the graph represent the data centers and the edges represent communication links A social network can be modeled using a graph in which individuals or organizations are represented by vertices relationships between individuals or organizations are represented by edges The WorldWideWeb can be modeled as a directed graph where each Web …