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 n₀ & c such that to the right of n₀, the value of f(n) always lies on or below cg(n).

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(n²), but O (n) is asymptotically tight while O(n²) 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

Ask an Expert

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

Write your message here..

Related Questions

Depth First Search Through Un-weighted Connected Graph , Q. Write down the ... Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

Sparse matrix, How sparse matrix stored in the memory of a computer? How sparse matrix stored in the memory of a computer?

File organization, Define File organization''s and it''s types Define File organization''s and it''s types

Procedure to delete all terminal nodes of the tree, Q. Let a binary tree 'T... Q. Let a binary tree 'T' be in memory. Write a procedure to delete all terminal nodes of the tree.       A n s . fun ction to Delete Terminal Nodes from Binary Tree

Merging, Merging two sequence using CREW merge Merging two sequence using CREW merge

Frequency count, what is frequency count what is frequency count

Inorder traversal, Inorder traversal: The left sub tree is visited, then t... Inorder traversal: The left sub tree is visited, then the node and then right sub-tree. Algorithm for inorder traversal is following: traverse left sub-tree visit node

Objectives of lists, After going through this unit, you will be able to: ... After going through this unit, you will be able to: • define and declare Lists; • understand the terminology of Singly linked lists; • understand the terminology of Doubly

Complexity of algorithm, The simplest implementation of the Dijkstra's algo... The simplest implementation of the Dijkstra's algorithm stores vertices of set Q into an ordinary linked list or array, and operation Extract-Min(Q) is just a linear search through

Surrounding of sub division method, Surrounding of sub division method ... Surrounding of sub division method A polygon surrounds a viewport if it completely encloses or covers the viewport. This happens if none of its sides cuts any edge of the viewp