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

Stacks are often used in evaluation of arithmetic expressions. An arithmetic expression contains operands & operators. Polish notations are evaluated through stacks. Conversions of

Operations on B-Trees Given are various operations which can be performed on B-Trees: Search Create Insert B-Tree does effort to minimize disk access and t

Explain about Hidden-surface Hidden-line removal refers to wire-frame diagrams without surface rendering and polygonal surfaces with straight edges. Hidden-surface removal ref

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

Define a sparse metrics. A matrix in which number of zero entries are much higher than the number of non zero entries is known as sparse matrix. The natural method of showing m

HSV Colour Model Instead of a set of colour primaries, the HSV model uses colour descriptions that have a more intuitive appeal to a user. To give a colour specification, a use

Define min-heap A min-heap is a complete binary tree in which each element is less than or equal to its children. All the principal properties of heaps remain valid for min-hea

Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node