ASSIGNMENT NO. 2

1. ANALYSIS OF ALGORITHM


Analysis of algorithm  is to determine the amount of resources (such as time and storage) necessary to execute it.  It is to analyse an algorithm. It  is a field in computer science whose overall goal is an understanding of the complexity of algorithms. The practical goal of algorithm analysis is to predict the performance of different algorithms in order to guide program design decisions.


2. EMPIRICAL ANALYSIS


Empirical Analysis is what we observe or experiment. It means that it is an observation on what we analyse on a certain algorithm and we can determine whats the best algorithm to use.



Steps for Empirical Analysis
a. Decide on the basic operation.
b. Decide on the input sample (range, size,...).
c. Convert the algorithm to a program.
d. Generate a sample of inputs.
e. Run the program; record the observed data.
f. Analyze the data.


3. BIG OH NOTATION


Big oh notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. It describe the performance or complexity of an algorithm. 


Some common orders of growth along with descriptions:

O(1)

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

O(N)

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

O(N²)

O(N²) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴) etc.

O(2^N)

O(2^N) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^N) function will quickly become very large.