Analysis of Algorithms

Adapted from the Goodrich and Tamassia viewgraphs on Analysis of Algorithms

---

A Quick Math Review

• Logarithms and exponents

• properties of logarithms:

• properties of exponentials:

---

A Quick Math Review (cont.)

• Floor

• Ceiling
 

• Summations

• general definition:

• where f is a function, s is the start index, and t is the end index.

• Geometric progression:

• a summation where f(i) = aⁱ
• given an integer  and a real number ,

• geometric progressions exhibit exponential growth.

---

A Quick Math Review (cont.)

• Arithmetic progressions:

• An example

• two visual representations

---

Forward Proof of Geometric Progression

                                     (1)

Multiply (1) by –a

                            (2)

Add (1) and (2) Divide by (1-a)
Special case of a=2:

---

Simple Justification Techniques



By Example: Can only be used to justify claims of a generic nature. Often part of a larger justification.
Claim: $ real numbers c > 0 and n₀ ³ 1 for which 
Justification: Choose n₀ = 1 and c = 7.
 
By Counter-Example:To disprove a bogus claim, a counter-example is all that is necessary.

False claim: Every number 2ⁱ – 1, where i is a positive integer, is a prime number.

Disproof: 2⁴ – 1 = 16 – 1 = 15 = 5× 3, which is not a prime number. Therefore the claim is not true.

---

Simple Justification Techniques (cont.)



By Contradiction – Suppose that the claim is not true. Show that this assumption leads to an inconsistency.
Claim: There is no biggest positive integer.
Justification: Suppose B is the biggest positive integer. Now let A = B + 1. Note that A > B.
Þ B cannot be the biggest positive integer.
 
Contra-Positive:
Claim: If A is true then B is true.
Justification: Show that if B is not true then A cannot be true.

---

Proofs by Induction Show that property P is true for all integers .
Basis: Prove that P is true for n₀.
Inductive hypothesis: Assume that P is true for all . Prove that P is also true for k = n.
Example: arithmetic progression
. Basis: S(1) = 1(1 + 1)/2 = 1. OK
Inductive hypothesis: .

---

Advanced Topics: Other Justification Techniques

• Proof by excessive waving of hands.

• Proof by incomprehensible diagrams.

• Proof by very large bribes.
• See instructor after class.

• The Emperor's New Clothes Method
• "This proof is so obvious that only an idiot wouldn't be able to understand it.

---

Measuring the Running Time

• How should we measure the running time of an algorithm?

• Experimental Study

• Write a program that implements the algorithm.
• Run the program with data sets of varying size and composition.
• Use a method like System.currentTimeMillis() to get an accurate measure of the actual running time.
• The resulting data set should look something like:

---

Beyond Experimental Studies

• Experimental studies have several limitations:
• It is necessary to implement and test the algorithm in order to determine its running time.
• Experimental studies can be done only on a limited set of inputs and 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 should be used.

• We shall now develop a general methodology for analyzing the running time of algorithms that
• Uses a high-level description of the algorithm instead of testing one of its implementations.
• Takes into account all possible inputs.
• Allows us to evaluate the efficiency of any algorithm in a manner that is independent from the hardware and software environment.

---

What is Pseudo-Code?

• A mixture of natural language and high-level programming concepts that describes the main ideas behind a generic implementation of a data structure or algorithm.
• Expressions: use standard mathematical symbols to describe numeric and boolean expressions.
• use ¬ for assignment ("=" in Java).
• use = or == for equality testing ("==" in Java).
• Method declarations:
• Algorithm name(param1, param2)
• Programming constructs:
• decision constructs: if … then … [else …]
• while loops: while … do
• repeat loops: repeat … do
• for loops: for … do
• array indexing A[i]
• Methods (Algorithms):
• calls: name(args…)
• returns: return value

---

Pseudo-Code (cont.)

• Pseudo-code is a description of an algorithm that is more structured than prose but less formal than a programming language.

• Example: finding the maximum element of an array.

Algorithm arrayMax(A, n):
Input: An array A storing n integers
Output: The maximum element in A. currentMax ¬ A[0]
for i ¬ 1 to n-1 do if currentMax < A[i] then currentMax ¬A[i] return currentMax

• Pseudo-code is our preferred notation for describing algorithms.
• However, pseudo-code hides some program design and implementation issues.

---

Analysis of Algorithms

• Primitive Operation: Low-level computations that are largely independent from the programming language and can be identified in pseudocode, e.g.
• calling a method and returning from a method
• performing an arithmetic operation (e.g., addition or subtraction).
• comparing two numbers
• indexing into an array
• following an object method
• returning from a method.

• By inspecting the pseudo-code, we can count the number of primitive operations executed by an algorithm.

• Recall the arrayMax example (previous viewgraph).

---

Average Case vs. Worst Case Running Time of an Algorithm

• An algorithm may run faster on certain data sets than on others.

• Finding the average case can be very difficult, so typically algorithms are measured by worst-case time complexity.

• Also, in certain applications domains (e.g., air traffic control, surgery) knowing the worst-case time complexity is of crucial importance.

---

Asymptotic Notation Big-Oh:

• Given

• Functions f and g defined over non-negative integers, and
• real constants c and n₀,

• we define big-Oh as follows:

• 

---

Examples of Big-Oh Example: 7n – 3 is O(n)
Justification:

satisfies this inequality.

Example:
Justification:

$ c,n₀ such that

Since
we can write

Thus c = 35 and n₀ = 1.

---

Asymptotic Notation (cont.)

• Note: Even though it is true that 7n-3 is O(n⁵), the big-Oh characterization should be of as small an order as possible.

• Simple Rule: Drop lower order terms and constant factors.

• 
• 

• Special classes of algorithms:

• constant time   O(1)
• logarithmic      O(log n)
• linear              O(n)
• n log n            O(n log n)
• quadratic        O(n²)
• polynomial      O(n^k), k > 1
• exponential     O(aⁿ), n > 1

• "Relatives" of big-Oh:
• W (g(n)): big Omega
• Q (g(n)): big Theta

---

Big Omega Definition:

Illustration:

 

---

Big Theta Definition:

Illustration

---

Asymptotic Analysis of Running Time

• Use the big-Oh notation to express the number of primitive operations executed as a function of the input size n.

• For example, we say that the arrayMax algorithm runs in O(n) time.

• Comparing the asymptotic running time,

• an algorithm that runs in O(n) time is generally better than one that runs in O(n²) time.
• similarly, O(log n) is generally better than O(n).
• heirarchy of functions:
• 

• Caution!

• Beware of very large constant factors. An algorithm that runs in time 10⁹n is still O(n) but might be less efficient on your dataset than one runnning in time 2n², which is O(n²).

---

---

Example of Asymptotic Analysis (1)

• An algorithm for computing prefix averages:

Algorithm prefixAverages1(X)
Input: An n-element array X of numbers.
Output: An n-element array A of numbers such that A[i] is the average of elements X[0], …, X[i]. Let A be an array of n numbers.
for i ¬ 0 to n-1 do a ¬ 0
for j ¬ 0 to i do a ¬a + X[j] A[i] ¬a/(i+1) return array A

• Analysis …

---

Example of Asymptotic Analysis (2)

• An improved algorithm for computing prefix averages:

Algorithm prefixAverages2(X)
Input: An n-element array X of numbers.
Output: An n-element array A of numbers such that A[i] is the average of elements X[0], …, X[i]. Let A be an array of n numbers.
s ¬ 0
for i ¬ 0 to n-1 do s ¬s + X[i]
A[i] ¬s/(i+1) return array A

• Analysis …