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
Advantages of dry running a flowchart When dry running a flowchart it's advisable to draw up a trace table illustrating how variables change their values at every stage in the

Ordinary variable An ordinary variable of a easy data type can store a one element only

compare and contrast the bubble sort,quick sort,merge sort and radix sort

Algo rithm to Insert a Node p at the End of a Linked List is explained below Step1:   [check for space] If new1= NULL output "OVERFLOW" And exit Step2:   [Allocate fr

Which data structure is used for implementing recursion Stack.

Best - Fit Method: - This method obtains the smallest free block whose  size is greater than or equal to get such a block by traversing the whole free list follows.

Q. Explain that how do we implement two stacks in one array A[1..n] in such a way that neither the stack overflows unless the total number of elements in both stacks together is n.

Define an array. Array is made up of same data structure that exists in any language. Array is set of same data types. Array is the collection of same elements. These same elem

Thus far, we have been considering sorting depend on single keys. However, in real life applications, we may desire to sort the data on several keys. The simplest instance is that

Define Prim's Algorithm Prim's  algorithm  is  a  greedy  algorithm  for  constructing  a  minimum  spanning  tree  of  a  weighted linked graph. It works by attaching to a bef