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

Algorithm of binary search, Step 1: Declare array 'k' of size 'n' i.e. k(n)... Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

State the symbols of abstract data type operation, Symbols of ADT oepration... Symbols of ADT oeprations All Symbol ADT operations are implemented in Symbol class, except toSymbol(), which is implemented in classes (like String) which can generate a Symb

STACK, WHAT IS THE PURPOSE OF STACK IN C WHAT IS THE PURPOSE OF STACK IN C

Define doubly linked list, A list item stores pointers and an element ... A list item stores pointers and an element to predecessor and successor. We call a pointer to a list item a handle . This looks simple enough, but pointers are so powerful tha

Disadvantages of the lifo costing method, The disadvantages or limitations ... The disadvantages or limitations of the last in first out costing method are: The election of last in first out for income tax purposes is binding for all subsequent yea

Binary search tree, write an algorithm to delete an element x from binary... write an algorithm to delete an element x from binary search with time complex

Method to add an element in circular queue, Q. Let us consider a queue is h... Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet

Explain arrays, Arrays :- To execute a stack we need a variable called top,... 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.

Space and time complexity, why the space increase in less time programs why the space increase in less time programs

Compare and contrast various sorting techniques, Q. Compare and contrast va... Q. Compare and contrast various sorting techniques or methods with respect to the memory space and the computing time.