Use of asymptotic notation in the study of algorithm, Data Structure & Algorithms

Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.                                        

Ans:

The running time of the algorithm depends upon the number of characteristics and slight variation in the characteristics varies and affects the running time. The algorithm performance in comparison to alternate algorithm is best described by the order of growth of the running time of the algorithm. Let one algorithm for a problem has time complexity of c3n2 and another algorithm has c1n3 +c2n2 then it can be simply observed that the algorithm with complexity c3n2 will be faster compared to the one with complexity c1n3 +c2n2 for sufficiently larger values of n. Whatever be the value of c1, c2   and c3 there will be an 'n' past which the algorithm with the complexity c3n2 is quite faster than algorithm with complexity c1n3 +c2n2, we refer this n as the breakeven point. It is difficult to determine the correct breakeven point analytically, so asymptotic notation is introduced that describe the algorithm performance in a meaningful and impressive way. These notations describe the behaviour of time or space complexity for large characteristics. Some commonly used asymptotic notations are as follows:

1)      Big oh notation (O): The upper bound for a function 'f' is given by the big oh notation (O). Taking into consideration that 'g' is a function from the non-negative integers to the positive real numbers, we define O(g) as the set of function f such that for a number of real constant c>0 and some of the non negative integers constant n0  , f(n)≤cg(n) for all n≥n0. Mathematically, O(g(n))={f(n): hear exists positive constants such that 0≤f f(n)≤cg(n) for all n, n≥n0} , we say "f is oh of g".

2)      Big Omega notation (O): The lower bound for a function 'f' is given by the big omega notation (O). Considering 'g' is the function from the non-negative integers to the positive real numbers, hear we define O(g) as the set of function f  such that  for a number of real constant c>0 and a number of non negative integers constant n0  , f(n)≥cg(n) for all n≥n0. Mathematically, O(g(n))={f(n): here exists positive constants such that 0≤cg(n) ≤f(n) for all n, n≥n0}.

3)      Big Theta notation (θ):  The upper and lower bound for the function 'f' is given by the big oh notation (θ). Taking 'g' to be the function from the non-negative integers to the positive real numbers, here we define θ(g) as the set of function f  such that  for a number of real constant c1 and c2 >0 and a number of non negative integers constant n0  , c1g(n)≤f f(n)≤c2g(n) for all n≥n0. Mathematically, θ(g(n))={f(n): here exists positive constants c1 and c2 such that c1g(n)≤f f(n)≤c2g(n) for all n, n≥n0} , hence we say "f is oh of g"

Posted Date: 7/10/2012 6:17:26 AM | Location : United States







Related Discussions:- Use of asymptotic notation in the study of algorithm, Assignment Help, Ask Question on Use of asymptotic notation in the study of algorithm, Get Answer, Expert's Help, Use of asymptotic notation in the study of algorithm Discussions

Write discussion on Use of asymptotic notation in the study of algorithm
Your posts are moderated
Related Questions
an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Define min-heap A min-heap is a complete binary tree in which each element is less than or equal to its children. All the principal properties of heaps remain valid for min-hea

Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet

for i=1 to n if a[i}>7 for j=2 to n a[j]=a{j}+j for n=2 to n a[k]=a[j]+i else if a[1]>4 && a[1] for 2 to a[1] a[j]= a{j]+5 else for 2to n a[j]=a[j]+i ..

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

Conversion of Forest into Tree A binary tree may be used to show an entire forest, since the next pointer in the root of a tree can be used to point to the next tree of the for

Write an algorithm by using pseudocode which: Inputs top speeds of 5000 cars Outputs fastest speed and the slowest speed Outputs average speed of all the 5000 cars

We will start by defining a new structure called Heap. Figure 3 illustrates a Binary tree. Figure: A Binary Tree A complete binary tree is said to assure the 'heap con

I need help writing a pseudocode for my assignment can anyone help?

Construct a B+ tree for the following keys, starting with an empty tree.  Each node in the tree can hold a maximum of 2 entries (i.e., order d = 1). Start with an empty root nod