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

Assignment Help:

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"


Related Discussions:- Use of asymptotic notation in the study of algorithm

Bubble sort, In this sorting algorithm, multiple swapping occurs in one pas...

In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm. In this method,

Flowchart, create a flowchart that displays the students average score for ...

create a flowchart that displays the students average score for these quizzes

Pseudo code, I need help writing a pseudocode for my assignment can anyone ...

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

Determine the types of java, Determine the types of JAVA Java has two p...

Determine the types of JAVA Java has two parts... 1. Core language -- variables, arrays, objects o Java Virtual Machine (JVM) runs the core language o Core language is

Define game trees, Game trees An interesting application of trees is th...

Game trees An interesting application of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can picture the sequence of possible moves by m

Differentiate between nonpersistent and 1-persistent, Differentiate between...

Differentiate between Nonpersistent and 1-persistent Nonpersistent: If the medium is idle, transmit; if the medium is busy, wait an amount of time drawn from a probability dist

Define prims algorithm, Define Prim's Algorithm Prim's  algorithm  is  ...

Define Prim's Algorithm Prim's  algorithm  is  a  greedy  algorithm  for  constructing  a  minimum  spanning  tree  of  a  weighted linked graph. It works by attaching to a bef

Complexity, Complexity : How do the resource needs of a program or algorith...

Complexity : How do the resource needs of a program or algorithm scale (the growth of resource requirements as a function of input). In other words, what happens with the performan

Sorting, how to do a merge sorting

how to do a merge sorting

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd