Friday, February 4, 2011

__Assignment 2__

EMPIRICAL ANALYSIS

      As i go along and try to find the meaning of Empirical Analysis, most of them were complicated and i could not find the simplest meaning of it. So, I looked up the word "Empirical" in the dictionary. According to the source, the word EMPIRICAL means relying or based solely on experiment and observation rather than theory. As what I've understand is that Empirical Analysis is an analysis based on experiment or the result of an observed data.

ANALYSIS OF ALGORITHM

      When it talks about analysis of algorithm, the first thing comes to my mind a simple question "what is algorithm". So, algorithm basically it is a sequence of instructions or set of rules specifying how to solve a certain problem. When we say analysis of algorithm it is a field of computer science that deals to understand the complexity of algorithms. Generally, analysis of algorithm is most concerned with:

           - finding out how much time a program takes to run
           - how much memory storage space it needs to execute the program

 In computer scientists they use analysis of algorithm:

           - to determine how the data imputed into a program affects its total running time
           - how much memory space the computer needs for program data
           - how much space the program's code takes in the computer
           - whether an algorithm produces correct calculations
           - how complex a program is
           - how well it deals with unexpected results

      For me, algorithm is important because knowing it first before starting a certain problem or we say "you are planning to start your own company", finding a better algorithm can lead you to success.

Big - Oh NOTATION

      From what I've read and search, Big Oh notation is used to describe the efficiency of an algorithm. There are several other notations but Big Oh is the most common for computer science. In short it is a function that describes the worst case performance of an algorithm. Big Oh means given n inputs the algorithm uses O(x), pronounced O of x, resources. x is a function that depends on n. Generally we are measuring operations, and thus speed, but it can also be used for memory usage or many other metrics.  Big Oh is useful because it tells us the algorithm will never be any worse than this.

- Common Asymptotic Function

     a.) O(1) constant function
        - it requires a fixed number of steps and ignores the length like the push and pop  in the link list.
     b.) O(n) linear
        - unlike O(1), O(n) requires a number of steps like traversing the link list until end.
     c.) O(n^2) quadratic
        - This is referring to the proportion of the size of n operator like the 2 dimensional  arrays.  
     d.) O(log n) logarithmic
        -  inserting or removing a binary node or searching fir a specific node.
     e.) O(n log n) ---
        - sorting algorithm and faster than O(log n)
     f.)  O(a^n)(a>1) exponential
        - recursion algorithm like Fibonacci


Reference:
http://www.wisegeek.com/what-is-algorithm-analysis.htm
http://www.brpreiss.com/books/opus5/html/page36.html
http://www.wisegeek.com/related/?kw=Algorithm&rt=ChBNS-

http://www.yourdictionary.com/empirical
http://www.apcomputerscience.com/apcs/misc/BIG-O.pdf