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
In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

Do you have a library solution for this problem?

Q. Define a method for keeping two stacks within a single linear array S in such a way that neither stack overflows until entire array is used and a whole stack is never shifted to

Triangular Matrices Tiangular Matrices is of 2 types: a)  Lower triangular b)  Upper triangular

merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real

What is String Carrier set of the String ADT is the set of all finite sequences of characters from some alphabet, including empty sequence (the empty string). Operations on s

what are the charaterstics to determine weather an algorithm is good or not? explain in detail

How many nodes in a tree have no ancestors 1 node in atree have no ancestors.

The most common way to insert nodes to a general tree is to first discover the desired parent of the node you desire to insert, and then insert the node to the parent's child list.