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
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

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

WHAT IS THE PURPOSE OF STACK IN C

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

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

write an algorithm to delete an element x from binary search with time complex

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

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.


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