Empirical Analysis
From what I have research and read, empirical analysis is a kind of analysis which gives information based on experiments, observations or experience.
From the given definition above, it simply mean that empirical analysis is more on application of the given data. As I research, I come up with different set of examples in which I do not fully understand, but for you to be able to know, I have inserted some link that would help.
Analysis of Algorithm
When you say analysis of algorithm, it is the step by step procedure for solving a problem with a finite amount of time. Analysis algorithm is a computer field that deals about the algorithm and understand the complexity of an algorithm. Algorithm is a sequence of computational steps that transform the input data into useful output data.
Why do we need to analyze algorithm? Simple reason is to avoid performance bugs.
According to what I have read, analysis of algorithm is most commonly used on computational time to solve a given problem. You need the right analysis for this algorithm to be able to easily understand the formula.
· In order to learn more on algorithm…we must first analyze it. Analyze the algorithm if we have some of the data to analyze:
1. Determine the running time of the program as a function of its inputs.
2. Determine the total and the maximum memory space for the program.
3. Determine the total size of program code.
4. Determine whether you can get the right output from the program.
5. Determine whether the program can be read or understand clearly for accessing.
6. Determine the robustness of the program.
Big O notation
From what I have read, the Big O notation is a way of comparing two algorithms. The big O 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 has two main areas of application. In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic expansion. In computer science, it is useful in the analysis of algorithms. In both applications, the function g(x) appearing within the O(...) is typically chosen to be as simple as possible, omitting constant factors and lower order terms.
There are two formally close, but noticeably different, usages of this notation: infinite asymptotics and infinitesimal asymptotics. This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument.
Big o notation:
1. O(1)-constant time
-it requires a fixed number of steps and ignores the length like the push and pop in the link list.
2. O(n)-linear time
-unlike O (1), O (n) requires a number of steps like traversing the link list until end.
3. O(n^2) - quadratic time
-This is referring to the proportion of the size of n operator like the 2 dimensional arrays.
4. O(log n) - logarithmic time
-inserting or removing a binary node or searching fir a specific node.
5. O(n log n) - "n log n " time
-sorting algorithm and faster than O(log n).
6. O(a^n) (a > 1) - exponential time
-recursion algorithm like Fibonacci
An example:
Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
REFERENCES:
No comments:
Post a Comment