Big o notation, Data Structure & Algorithms

Assignment Help:

This notation gives an upper bound for a function to within a constant factor. Given Figure illustrates the plot of f(n) = O(g(n)) depend on big O notation. We write f(n) = O(g(n)) if there are positive constants n0 & c such that to the right of n0, the value of f(n) always lies on or below cg(n).

2388_The o-Notation.png

Figure: Plot of  f(n) = O(g(n))

Mathematically specking, for a given function g(n), we specified a set of functions through O(g(n)) by the following notation:

O(g(n)) = {f(n) :  There exists a positive constant c and n0 such that 0 ≤  f(n) ≤ cg(n)

for all n ≥ n0 }

Obviously, we employ O-notation to describe the upper bound onto a function using a constant factor c.

We can view from the earlier definition of Θ that Θ is a tighter notation in comparison of big-O notation. f(n) = an + c is O(n) is also O(n2), but O (n) is asymptotically tight while O(n2) is notation.

While in terms of Θ notation, the above function f(n) is Θ (n). Because of the reason big-O notation is upper bound of function, it is frequently used to define the worst case running time of algorithms.


Related Discussions:- Big o notation

Number of leaf nodes in a complete binary tree, The number of leaf nodes in...

The number of leaf nodes in a complete binary tree of depth d is    2 d

Non Recursive Algorithm to Traverse a Binary Tree, Q. Write down a non recu...

Q. Write down a non recursive algorithm to traverse a binary tree in order.                    Ans: N on - recursive algorithm to traverse a binary tree in inorder is as

Determine the comparison of gouraud and phong shading, Comparison of Gourau...

Comparison of Gouraud and Phong Shading Phong shading requires more calculations, but produces better results for specular reflection than Gouraud shading in the form of more r

Algorithm for pre-order traversal, Hear is given a set of input representin...

Hear is given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to give the output in three traversal orders. Write down an

Algorithm for a function that takes in integer as argument, Write a detaile...

Write a detailed description of a function that takes in an integer as an argument, then prints out the squares of all positive integers whose squares are less than the input. (The

Complexity of an algorithm, compare two functions n and 2n for various valu...

compare two functions n and 2n for various values of n. determine when second becomes larger than first

Infix expression into the postfix expression, Q. Write down an algorithm to...

Q. Write down an algorithm to convert an infix expression into the postfix expression.     Ans. Algo rithm to convert infix expression to post fix expression is given as

Explain the concept of hidden lines and surface removal, Explain the concep...

Explain the concept of hidden lines The problem of hidden lines or surfaces was implicit even in 2-D graphics, but we did not mention it there, because what was intended to be

Simplifying assumptions of wire frame representation, Simplifying Assumptio...

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

Define null values, Define null values.  In some cases a particular ent...

Define null values.  In some cases a particular entity might not have an applicable value for an attribute or if we do not know the value of an attribute for a particular entit

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