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
#question.explain different types of errors in data transmission.

For a queue a physical analogy is a line at booking counter. At booking counter, customers go to the rear (end) of the line & customers are attended to several services from the fr

A set s is conveniently shown in a computer store by its characteristic function C(s). This is an array of logical numbers whose ith element has the meaning "i is present in s". As

write an algorithm for multiplication of two sparse matrices using Linked Lists

Decision Tree - ID3 algorithm: Imagine you only ever do one of the following four things for any weekend:   go shopping   watch a movie   play tennis   just

Explain the theory of computational complexity A  problem's  intractability  remains  the  similar  for  all  principal  models  of   computations    and   all reasonable inpu


ALGORITHM (Insertion of element into a linked list) Step 1 Begin the program Step 2 if the list is empty or any new element comes before the start (head) element, then add t

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

The smallest element of an array's index is called its Lower bound.