Assignment 2

Empirical analysis


* It is a kind of analysis which denotes information gained by means of observation, experience or experiment.


It is easy to understand this kind of analysis. From the definition itself, it is more on experiments, observations and experiences. Easy to understand but there’s a lot of things to do like conducting experiments, observing things and learning from experiences.



ANALYSIS of ALGORITHM


* Algorithms are designed to work with inputs. The efficiency or the running time of an algorithm is stated as a function relating the input length to the number of steps or storage locations.


   Analysis of algorithm determines the amount of resources such as time and storage which are necessary to execute a program. It provides theoretical estimation for the resources needed by any algorithm solves a given computational problem and it is common to estimate their complexity. If you are given such an expression of an algorithm, we run the program and observe its behavior. But we must be careful in making conclusions based upon the performance of the program. In analyzing an algorithm, we will determine the following:

     - Running time of a program as a function of its inputs.

     - The total or maximum memory space needed for the data of the program.

     - The total size of the program code.

     - The complexity of the program which is the readability of the program and of how is it to understand. 

     - The robustness of the program. Of how will it deal with erroneous inputs.


But we are primarily concerned with the running time of a program. We have to consider the memory space needed to execute a program. There were many factors that will affect the running time. These are the algorithm itself, the input data, and the computer system used to run the program. The performance of a computer is determined by the hardware: the processor (type and speed), memory available and disk available, the programming language used to execute the program, the language compiler and interpreter, and the computer operating system software used.



Big O notation


* It is commonly used notation that seeks to describe the relative complexity of an algorithm, that is, for estimating the rate of function growth as the key factors tends towards infinity. Given two positive-valued functions f and g, consider the following definition: f(n) is O( g(n) ) if there exist positive numbers c and N such that f(n) is less than or equal to cg(n) for all n ≥ N.


The problem with this definition is that, it states only that there must exist certain c and N but it does not give any hint on how to compute or calculate the values these constants. Second, it does not put any limitations on these values and gives little guidance in situations when there are many candidate values. For example, for f (n) = 2n² + 3n +1 = O(n²) where g(n) = n².


sources:



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



http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one