Analysis of Algorithms

Analysis of Algorithms

• Algorithm

• Input

• Output

Outline

• Analysis of Algorithms

• Running time
• Pseudo-code
• Counting primitive operations
• Asymptotic notation
• Asymptotic analysis

How good is Insertion-Sort?

• Analysis of Algorithms

• How can you answer such questions?

What is “goodness”?

• Measure
• Count
• Estimate

• Analysis of Algorithms

• How can we quantify it?

• Correctness
• Minimum use of “time” + “space”

1) Measure it

• Analysis of Algorithms

• Write a program implementing the algorithm
• Run the program with inputs of varying size and composition
• Use a method like System.currentTimeMillis() to get an accurate measure of the actual running time
• Plot the results

• Analysis of Algorithms

Limitations of Experiments

• Analysis of Algorithms

• It is necessary to implement the algorithm, which may be difficult
• Results may not be indicative of the running time on other inputs not included in the experiment.
• In order to compare two algorithms, the same hardware and software environments must be used

2) Count Primitive Operations

• The Idea
• Write down the pseudocode
• Count the number of “primitive operations”

• Analysis of Algorithms

Pseudocode

• Analysis of Algorithms

• High-level description of an algorithm
• More structured than English prose
• Less detailed than a program
• Preferred notation for describing algorithms
• Hides program design issues

• Algorithm arrayMax(A, n)
• Input array A of n integers
• Output maximum element of A
• currentMax  A[0]
• for i  1 to n  1 do
• if A[i]  currentMax then
• currentMax  A[i]
• return currentMax

• Example: find max element of an array

Pseudocode Details

• Analysis of Algorithms

• Control flow
• if … then … [else …]
• while … do …
• repeat … until …
• for … do …
• Indentation replaces braces
• Method declaration
• Algorithm method (arg [, arg…])
• Input …
• Output …

• Method call
• var.method (arg [, arg…])
• Return value
• return expression
• Expressions
• Assignment (like  in Java)
• Equality testing (like  in Java)
• n2 Superscripts and other mathematical formatting allowed

The Random Access Machine (RAM) Model

• Analysis of Algorithms

• A CPU
• An potentially unbounded bank of memory cells, each of which can hold an arbitrary number or character

• 0

• 1

• 2

• Memory cells are numbered and accessing any cell in memory takes unit time.

Random Access Model (RAM)

• Time complexity (running time) = number of instructions executed
• Space complexity = the number of memory cells accessed

• Analysis of Algorithms

Primitive Operations

• Analysis of Algorithms

• Basic computations performed by an algorithm
• Identifiable in pseudocode
• Largely independent from the programming language
• Exact definition not important (we will see why later)

• Examples:
• Evaluating an expression
• Assigning a value to a variable
• Indexing into an array
• Calling a method
• Returning from a method

Analyzing pseudocode (by counting)

• For each line of pseudocode, count the number of primitive operations in it. Pay attention to the word "primitive" here; sorting an array is not a primitive operation.
• Multiply this count with the number of times this line is executed.
• Sum up over all lines.

• Analysis of Algorithms

Counting Primitive Operations

• Analysis of Algorithms

• By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size

• Algorithm arrayMax(A, n)
• Cost Times
• currentMax  A[0] 2 1
• for i  1 to n  1 do 2 n
• if A[i]  currentMax then 2 (n  1)
• currentMax  A[i] 2 (n  1)
• { increment counter i } 2 (n  1)
• return currentMax 1 1
• Total 8n  3

Estimating Running Time

• Analysis of Algorithms

• Algorithm arrayMax executes 8n  2 primitive operations in the worst case
• Define
• a Time taken by the fastest primitive operation
• b Time taken by the slowest primitive operation
• Let T(n) be the actual worst-case running time of arrayMax. We have a (8n  2)  T(n)  b(8n  2)
• Hence, the running time T(n) is bounded by two linear functions

Insertion Sort

• Analysis of Algorithms

• Hint:
• observe each line i can be implemented using a constant number of RAM instructions, Ci
• for each value of j in the outer loop, we let tj be the number of times that the while loop test in line 4 is executed. 

Insertion Sort

• Analysis of Algorithms

• Question: So what is the running time?

Time Complexity may depend on the input!

• Best Case:?
• Worst Case:?
• Average Case:?

• Analysis of Algorithms

Complexity may depend on the input!

• Best Case: Already sorted. tj=1. Running time = C * N (a linear function of N)
• Worst Case: Inverse order. tj=j.

• Analysis of Algorithms

Arithmetic Progression

• Analysis of Algorithms

• Neglecting the constants, the worst-base running time of insertion sort is proportional to 1 2 …n
• The sum of the first n integers is n(n 1) 2
• Thus, algorithm insertion sort required almost n2 operations.