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
what is far and near procedures in system programming?

Write the algorithm for compound interest

Encryption the plain-text using the round keys: 1. (Key schedule) Implement an algorithm that will take a 128 bit key and generate the round keys for the AES encryption/decryp

include include include /* Definition of structure node */ typedef struct node { int data; struct node *next; } ; /* Definition of push function */

Q. The system allocates the memory for any of the multidimensional array from a big single dimensional array. Describe two mapping schemes that help us to store the two dimensi

Program segment for All pairs shortest paths algorithm AllPairsShortestPaths(int N, Matrix C, Matrix P, Matrix D) { int i, j, k if i = j then C[i][j] = 0  for ( i =

what''s queue ?

Need help with Data Structures assignment requiring C++ program

Now, consider a function that calculates partial sum of an integer n. int psum(int n) { int i, partial_sum; partial_sum = 0;                                           /* L

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem