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
floyd warshall algorithm

Thread By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using either a stack

Determine about the logic gates Many electronic circuits operate using binary logic gates. Logic gates essentially process signals that represent true or false or equivalent i.

Problem 1. Explain about the doubly linked list with neat diagram. Diagram Explaining doubly linked list 2. Explain what are the criteria to be used in evaluatin

Declaring a two dimensional array   A two dimensional array is declared same to the way we declare a one-dimensional array except that we state the number of elements in both di

Q. Devise a representation for a given list where insertions and deletions can be made at both the ends. Such a structure is called Deque (which means Double ended queue). Write fu

P os t - o r d e r T r av er sal :  This can be done by both iteratively and recursively. The iterative solution would require a modification or alteration of the in-

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

Programming for hash table?

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order