Omega notation, Data Structure & Algorithms

The ?-Notation (Lower Bound)

This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n0 and c such that to the right of n0, value of f(n) always lies on or above cg(n). Figure illustrates the plot of f(n) = ?(g(n)).

369_Omega Notation.png

Figure: Plot of  f(n) = ?(g(n))

Mathematically specking, for a given function g(n), we might define ?(g(n)) as the set of functions.

?(g(n)) = { f(n) : there presents constant c & n0 ≥ 0 such that 0 ≤  cg(n) ≤ f(n) for every n ≥ n0 }.

As ? notation define lower bound, it is utilized to bind the best case running time of an algorithm.

Posted Date: 4/4/2013 5:45:39 AM | Location : United States







Related Discussions:- Omega notation, Assignment Help, Ask Question on Omega notation, Get Answer, Expert's Help, Omega notation Discussions

Write discussion on Omega notation
Your posts are moderated
Related Questions
Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

Q. Take an array A[20, 10] of your own. Suppose 4 words per memory cell and the base address of array A is 100. Find the address of A[11, 5] supposed row major storage.

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)

what is the impoartance of average case analysis of algorithm

Define Complete Binary Tree Complete Binary Tree:- A whole binary tree of depth d is that strictly binary tree all of whose leaves are at level D.

1) What will call a graph that have no cycle? 2) Adjacency matrix of an undirected graph is------------- on main diagonal. 3) Represent the following graphs by adjacency matr

State  in brief about assertion Assertion: A statement which should be true at a designated point in a program.

Maximum numbers of nodes a binary tree of depth d The maximum numbers of nodes a binary tree of depth d can have is 2 d+1 -1.