Empirical Analysis
Empirical analysis is a kind of analysis wherein, it determines the amount of the resources needed to execute a program. In Empirical Analysis, you will need to decide to what kind of operations you will need to use in order to have an efficient program that will only consume a little space or time. Empirical analysis also implies on the decision of the user on what will be the input sample. Input sample means the storage and the limitations of the algorithm in a program. Empirical analysis means that an algorithm will be analyzed in a way that it will be shown on a step by step process so that the algorithm of the program will be efficient and be readable for the user.
Analysis of Algorithm
Analysis of algorithm means that a specific algorithm will be analyzed in a step by step process. To solve certain problems. It determines the running time of the program as a function of its inputs. It also determine the maximum space needed in a program or to run a program. In analysis of algorithm, it will determine the maximum memory needed in a source code. Analysis of algorithm is very important because it will makes the program or the algorithm be readable to the user. Analysis of algorithm also depends on the hardware used. It depends upon the processor, disk space, and memory of the system to handle an algorithm.
Big-oh analysis
| Notation | Name | Example |
| O(1) | Determining if a number is even or odd; using a constant-size lookup table or hash table | |
| O(log n) | Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap. | |
 | fractional power | Searching in a kd-tree |
 | Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry. | |
 | linearithmic, loglinear, or quasilinear | Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort |
| O(n2) | Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), shell sort, quicksort (worst case), selection sort or insertion sort | |
 | polynomial or algebraic | Tree-adjoining grammar parsing; maximum matching for bipartite graphs |
| | Factoring a number using the quadratic sieve or number field sieve | |
 | Finding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search | |
 | Solving the traveling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors. |
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used by an algorithm.
References:
gcu.googlecode.com/files/Analysis%20of%20Algorithms%20I.ppt
0 comments:
Post a Comment