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
Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

W h at are the different ways by which we can represent graph?  Represent the graph drawn below using those ways.     T he d iff e r e nt w a y s by

In this unit, we discussed Binary Search Trees, AVL trees and B-trees. The outstanding feature of Binary Search Trees is that all of the elements of the left subtree of the root

Consider the following 5-city traveling salesman problem. The distance between each city (in miles) is shown in the following table: (a) Formulate an IP whose solution will

A graph G might be defined as a finite set V of vertices & a set E of edges (pair of connected vertices). The notation utilized is as follows: Graph G = (V, E) Consider the g

Typical programming languages such as Pascal, C or Java give primitive data kinds such as integers, boolean, reals values and strings. They give these to be organised into arrays,

* Initialise d & pi* for each vertex v within V( g ) g.d[v] := infinity  g.pi[v] := nil g.d[s] := 0; * Set S to empty * S := { 0 }  Q := V(g) * While (V-S)

In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st

If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your mission (sho

how to implement multiple stack using single dimension array in c