Big o notation, Data Structure & Algorithms

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.

Posted Date: 4/4/2013 5:44:26 AM | Location : United States







Related Discussions:- Big o notation, Assignment Help, Ask Question on Big o notation, Get Answer, Expert's Help, Big o notation Discussions

Write discussion on Big o notation
Your posts are moderated
Related Questions
A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

In a circular linked list There is no beginning and no end.

Define the External Path Length The External Path Length E of an extended binary tree is explained as the sum of the lengths of the paths - taken over all external nodes- from

Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

2. Write a note on i) devising ii) validating and iii) testing of algorithms.

Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

Asymptotic Analysis Asymptotic analysis is depending on the idea that as the problem size grows, the complexity can be defined as a simple proportionality to some known functio

In this unit, we described about the data structure Queue. It had two ends. One is front from where the elements can be removed and the other is rear where the elements can be inse

Ask question #sdgsdgsdginimum 100 words accepted#

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