Assignment II: Empirical Analysis, Analysis Algorithm and Big-Oh Notation

Empirical Analysis of Algorithms

*empirical denotes information gained by means of observation, experience, or experiment

- tells about a specific implementation of the

abstract algorithm, so you have to be careful about what conclusions you can

draw about an algorithm’s efficiency from the empirical analysis of a specific

implementation. (For deciding on the time it takes to check membership in a

set, did you implement your set as a list, a hash table, ...?)

-its strength lies in its applicability to any

algorithm, but its results can depend on the particular sample of instances

and the computer used in the experiment.

- the principal alternative of mathematical analysis.

The General Plan

1. Decide on the efficiency metric M to be measured and the measurement unit

(an operation’s count vs. a time unit).

2. Decide on characteristics of the input sample (its range, size, and so on).

3. Prepare a program implementing the algorithm for the experimentation.

4. Generate a sample of inputs.

5. Run the algorithm on the sample inputs and record the data observed.

6. Analyze the data obtained.

http://www.clear.rice.edu/comp182/class/Slides-Set5.pdf

http://www.cameron.edu/~moinian/cs3713/slide-2.6.pdf

Analysis Algorithms

-An algorithm is a step- by- step procedure for solving a problem in a finite amount of time

-In mathematics and computer science, an algorithm is an effective method expressed as a finite list.

In order to learn more about an algorithm, we can ``analyze'' it. By this we mean to study the specification of the algorithm and to draw conclusions about how the implementation of that algorithm--the program--will perform in general. But what can we analyze? We can

• determine the running time of a program as a function of its inputs;
• determine the total or maximum memory space needed for program data;
• determine the total size of the program code;
• determine whether the program correctly computes the desired result;
• determine the complexity of the program--e.g., how easy is it to read, understand, and modify; and,
• determine the robustness of the program--e.g., how well does it deal with unexpected or erroneous inputs?

http://en.wikipedia.org/wiki/Algorithm

http://ww3.algorithmdesign.net/handouts/Analysis.pdf

Big-oh Notation

w Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that

f(n) £ cg(n) for n ³ n0

Big-Oh Rules

-If is f(n) a polynomial of degree d, then f(n) is O(nd), i.e.,

Drop lower-order terms

Drop constant factors

-Use the smallest possible class of functions

Say “2n is O(n)” instead of “2n is O(n2)”

-Use the simplest expression of the class

Say “3n+ 5 is O(n)” instead of “3n + 5 is O(3n)”

O(l) - constant time

This means that the algorithm requires the same fixed number of steps regardless of the size of the task.

Examples (assuming a reasonable implementation of the task):

A. Push and Pop operations for a stack (containing n elements);

B. Insert and Remove operations for a queue.

II. O(n) - linear time

This means that the algorithm requires a number of steps proportional to the size of the task.

Examples (assuming a reasonable implementation of the task):

A. Traversal of a list (a linked list or an array) with n elements;

B. Finding the maximum or minimum element in a list, or sequential search in an unsorted list of n elements;

C. Traversal of a tree with n nodes;

D. Calculating iteratively n-factorial; finding iteratively the nth Fibonacci number.

III. O(n2) - quadratic time

The number of operations is proportional to the size of the task squared.

Examples:

A. Some more simplistic sorting algorithms, for instance a selection sort of n elements;

B. Comparing two two-dimensional arrays of size n by n;

C. Finding duplicates in an unsorted list of n elements (implemented with two nested loops).

IV. O(log n) - logarithmic time

Examples:

A. Binary search in a sorted list of n elements;

B. Insert and Find operations for a binary search tree with n nodes;

C. Insert and Remove operations for a heap with n nodes.

V. O(n log n) - "n log n " time

Examples:

A. More advanced sorting algorithms - quicksort, mergesort

VI. O(an) (a > 1) - exponential time

Examples:

A. Recursive Fibonacci implementation

B. Towers of Hanoi

C. Generating all permutations of n symbols

The best time in the above list is obviously constant time, and the worst is exponential time which, as we have seen, quickly overwhelms even the fastest computers even for relatively small n. Polynomial growth (linear, quadratic, cubic, etc.) is considered manageable as compared to exponential growth.

http://ww3.algorithmdesign.net/handouts/Analysis.pdf

http://recursive-design.com/blog/2010/12/07/comp-sci-101-big-o-notation/