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
the deference between insertion,selection and bubble sort

Loops There are 3 common ways of performing a looping function: for ... to ... next, while ... endwhile and repeat ... until The below example input 100 numbers and find

Ask queConsider the following functional dependencies: Applicant_ID -> Applicant_Name Applicant_ID -> Applicant_Address Position_ID -> Positoin_Title Position_ID -> Date_Position_O


Q. Sort the sequence written below of keys using merge sort. 66, 77, 11, 88, 99, 22, 33, 44, 55                                                                      Ans:

WHAT IS THE PURPOSE OF STACK IN C

Merging two sequence using CREW merge

A representation of an array structure is a mapping of the (abstract) array with elements of type T onto the store which is an array with elements of type BYTE. The array could be

Explain in detail the algorithmic implementation of multiple stacks.

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.